お題: Java 30byte FizzBuzz - プログラマーの脳みそ
ぎ「FizzBuzzが110文字で書けるなら、1文字2bitの文字コードで記述すれば220bitで記述できる。byteに直すと28byteになる」
な「無茶言うなあ」
せ「だいたい、1文字2bitじゃ文字が4種類しか扱えないじゃない」
じゃあ、まじめに「1文字単位でちゃんと符号化できる」という縛りなら、実際何bitならFizzBuzzが記述できるかやってみた。
結果
FizzBuzz(97文字)は35種類の文字で書けて、上手く符号化すると59バイトになるよ。
daphne:FizzBuzz terazzo$ ls -l src/z.java -rw-r--r-- 1 terazzo admin 59 Feb 12 00:01 src/z.java
javacでコンパイル可能。javac自身が使うクラスパスは「-J-classpath -J<パス>」で指定する。*1
daphne:FizzBuzz terazzo$ javac -J-classpath -Jlib/fizzbuzzcharsets.jar -encoding FizzBuzz -d classes src/z.java daphne:FizzBuzz terazzo$ ls -l classes/z.class -rw-r--r-- 1 terazzo admin 893 Feb 11 23:58 classes/z.class
実行する。
daphne:FizzBuzz terazzo$ java -classpath classes z 1 2 Fizz 4 Buzz … 98 Fizz Buzz Exception in thread "main" java.lang.NoSuchMethodError: main daphne:FizzBuzz terazzo$
文字コード名はFizzBuzzだよ。Eclipse上で編集も出来るよ。
以下は過程だよ。
- FizzBuzzコードの短縮
- 文字種の削減
- 符号化方法の決定
- 文字セットプロバイダの実装(骨格部分)
- 文字セットプロバイダの実装(文字の変換表)
- 文字セットプロバイダの実装(bit操作)
- 文字セットプロバイダの実装(Encoder/DecodeおよびHelperの実装)
- SPIファイルの用意
FizzBuzzコードの短縮
まずリンク先の変態的なコードをみてみる。
class F{ static{ for(int i=1;i<101;i++){ System.out.println((i%3==0)?"Fizz":""+((i%5>0)?(i%3>0)?i:"":"Buzz")); } } }
これが 134 bytes。
うちのjavacだと「+」の方が優先度が高くて上手く動かないので括弧の位置移動。
class F{ static{ for(int i=1;i<101;i++){ System.out.println((i%3==0?"Fizz":"")+(i%5>0?i%3>0?i:"":"Buzz")); } } }
130バイト。改行と余分な空白をすべて削除。
class F{static{for(int i=1;i<101;i++){System.out.println((i%3==0?"Fizz":"")+(i%5>0?i%3>0?i:"":"Buzz"));}}}
106バイト。i++とか使う時にやればいいよね。
class F{static{for(int i=0;i++<100;){System.out.println((i%3==0?"Fizz":"")+(i%5>0?i%3>0?i:"":"Buzz"));}}}
105バイト。==0の代わりに<1にしてみる。
class F{static{for(int i=0;i++<100;){System.out.println((i%3<0?"Fizz":"")+(i%5>0?i%3>0?i:"":"Buzz"));}}}
104バイト。classじゃなくてenumにしたら……サイズは変わらないけど。
enum F{;static{for(int i=0;i++<100;){System.out.println((i%3<1?"Fizz":"")+(i%5>0?i%3>0?i:"":"Buzz"));}}}
あれ？enumなら1文字の列挙子でインスタンス初期化してくれたかも。staticが無くせる。
enum F{f;{for(int i=0;i++<100;){System.out.println((i%3<1?"Fizz":"")+(i%5>0?i%3>0?i:"":"Buzz"));}}}
これで99文字。
得意満面でぐぐったらenumのインスタンス初期化子を使うのは割と定石らしい……
FizzBuzz - nn_xの日記
data order@Java wizさんの解が公開になり、なぞが明らかになった。enum の Instance Initializer だった。
ほぼ答えも書いてあった……。
あとJavaのfor文はぶら下がり可なので{}を無くして97バイト
文字種の削減
符号化した時に短くなりやすくするために文字種を減らしてみる。
クラス名と列挙子とループ用の変数は同じ文字でいいよね。符号化の都合上なるべく偏ってる方が良い。
zは最低でも4個あるのでzに寄せておく。
enum z{z;{for(int z=0;z++<100;)System.out.println((z%3<1?"Fizz":"")+(z%5>0?z%3>0?z:"":"Buzz"));}}
「<」と「>」があるのが邪魔なので「<」だけにする
enum z{z;{for(int z=0;z++<100;)System.out.println((z%3<1?"Fizz":"")+(z%5<1?"Buzz":z%3<1?"":z));}}
符号化方法の決定
このソースコードを表現するのにベストな文字コード(というか符号化方法)を考える。
上記のFizzBuzzには35種類の文字が使われているのだけど、均等に割り振ると、1文字に6ビット必要になる。つまり97文字を73バイトまでしか減らせない。
符号は可変長ありとすると、「沢山使われている文字に短いビットを割り振る」ことで、全体のバイト数を減らせる。沢山出てくるやつに短いビットを割り当てる方法のポピュラーなものに「ハフマン符号化」というのがあるので、それをベースにする。
ハフマン符号 - Wikipedia
このルールに従って、出てくる文字にビットを割り当ててやる。算出部分は省略。
#文字,出現回数, 符号
'z', 12, 000
'"', 8, 0010
'1', 4, 0011
';', 4, 0100
'<', 4, 0101
'n', 4, 0110
' ', 2, 01110
'%', 3, 01111
'(', 4, 10000
')', 4, 10001
'+', 3, 10010
'0', 3, 10011
':', 3, 10100
'?', 3, 10101
'i', 3, 10110
't', 4, 10111
'u', 3, 11000
'.', 2, 110010
'3', 2, 110011
'5', 1, 110100
'e', 2, 110101
'm', 2, 110110
'o', 2, 110111
'r', 2, 111000
'{', 2, 111001
'}', 2, 111010
'=', 1, 1110110
'B', 1, 1110111
'F', 1, 1111000
'S', 1, 1111001
'f', 1, 1111010
'l', 1, 1111011
'p', 1, 1111100
's', 1, 1111101
'y', 1, 1111110zは計画通り一番沢山出てくるので3ビットを割り当てる。BとかZは一回しか出ないのでしかたなく7ビットにする。
Unicode全体が符号化できるように、ここに無い文字については、「0xff」(11111111)をエスケープ文字ということにして、その後ろにUTF-8でのバイト列を続けることにする。
「日本語」(E697A5 E69CAC E8AA9E)なら「FFE697A5 FFE69CAC FFE8AA9E」になる。
当然中途半端な位置からエスケープが始まる場合もある。
「"日本語"」なら「"」は上の表通り4ビットの2(0010)に圧縮されるので、4ビット分ずれて「2FFE697A 5FFE69CA CFFE8AA9 E2」のようになる。
なお最後のバイトが半端な長さになっている場合は、足りないビットは1でパディングする。
文字セットプロバイダの実装(骨格部分)
http://www.utilz.jp/wiki/Charsetを見ながら実装していく。
まずキャラクタセットサービスプロバイダクラスとキャラクタセットクラス。
package sample.charset; import java.nio.charset.Charset; import java.nio.charset.spi.CharsetProvider; import java.util.Arrays; import java.util.Iterator; public class FizzBuzzCharsetProvider extends CharsetProvider { private Charset charset = new FizzBuzzCharset(); public Charset charsetForName(String charsetName) { return charsetName.equals(FizzBuzzCharset.CHARSET_NAME) ? charset : null; } public Iterator<Charset> charsets() { return Arrays.asList(charset).iterator(); } }
package sample.charset; import java.nio.charset.Charset; import java.nio.charset.CharsetDecoder; import java.nio.charset.CharsetEncoder; public class FizzBuzzCharset extends Charset { public static final String CHARSET_NAME = "FizzBuzz"; protected FizzBuzzCharset() { super(CHARSET_NAME, null); } @Override public boolean contains(Charset cs) { return true; } @Override public CharsetDecoder newDecoder() { return new FizzBuzzCharsetDecoder(this); } @Override public CharsetEncoder newEncoder() { return new FizzBuzzCharsetEncoder(this); } }
次にCharsetEncoderとCharsetDecoderの実装クラスだけど……なんかjava.nio.Bufferとかを使っていて面倒くさい。*2
CharsetEncoderだと、継承してencodeLoop()というメソッドを実装すればいいらしい。
public CoderResult encodeLoop(CharBuffer in, ByteBuffer out) { try { // ループしながらinから読み込んでoutに書き出す。 // 途中でinが足りなくなったらCoderResult.UNDERFLOWを戻す // 途中でoutが足りなくなったらCoderResult.OVERFLOWを戻す } finally { // 読み出し/書き込み中バッファが足りなくなったらバッファーの位置を読み出し/書き込み前に戻す } }
途中でCharBufferが足りなくなったりByteBufferが足りなくなったりするので、一旦ループから抜けて補充してもらうという方式らしい。
ようするにこういう感じだよね。
public CoderResult encodeLoop(CharBuffer in, ByteBuffer out) { // スタート時の位置を記憶 in.mark(); out.mark(); try { while (true) { /* 読み取りをおこなう！！ */ if (/* 読み込み用バッファが足りなくて読み込めなかったら？ */) { return CoderResult.UNDERFLOW; } /* charからbyte[]に変換！！ */ /* 書き込みをおこなう！！ */ if (/* 書き込み用バッファが足りなくて書き込めなかったら？ */) { return CoderResult.OVERFLOW; } // 位置を確定してループを続行する in.mark(); out.mark(); } } finally { // 位置を最後に確定した状態に戻す in.reset(); out.reset(); } }
Bufferはposition, mark, limitという、現在の位置を表すフィールドを持っている。
positionが「ここまで読んだ(書いた)」という現在のシーク位置を表している。
mark()というのが、現在のpositionをチェックポイントに設定するメソッドで、reset()がpositionをチェックポイントまで巻き戻すメソッドになる。
limitというのがバッファの使用できる領域の最後を表していて、remaining()でlimitまでの数を取得できる。数の単位はByteBufferならバイト数だし、CharBufferなら文字数になる。
CharsetDecoderのdecodeLoop()もほぼ同じ構造で、但し読み出し元がByteBufferで書き込み先がCharBufferと逆になっている。
public CoderResult decodeLoop(ByteBuffer in, CharBuffer out) { ... }
おなじものを二回実装するのは嫌なので、テンプレートメッソドパターンかなにかでまとめたい。
残念なCharsetDecoder／CharsetEncoderはそれぞれのabstractクラスを継承して作ることになっているので、処理の部分は別クラスに実装して委譲するようにする。
class FizzBuzzCharsetEncoder extends CharsetEncoder { private static CharsetProcessor<CharBuffer, ByteBuffer> ENCODE_HELPER = new EncodeHelper(); /** ビット書き出しの際に端数分を保持する為のByteFragment */ private ByteFragment fragment = new ByteFragment(); ... /** encodeLoop()の実装。EncodeHelperに委譲 */ @Override protected CoderResult encodeLoop(CharBuffer in, ByteBuffer out) { return ENCODE_HELPER.doLoop(in, out, fragment); } ...
class FizzBuzzCharsetDecoder extends CharsetDecoder { private static CharsetProcessor<ByteBuffer, CharBuffer> DECODE_HELPER = new DecodeHelper(); /** ビット読み込みの際に端数分を保持する為のByteFragment */ private ByteFragment fragment = new ByteFragment(); ... /** decodeLoop()の実装。DecodeHelperに委譲 */ @Override protected CoderResult decodeLoop(ByteBuffer in, CharBuffer out) { return DECODE_HELPER.doLoop(in, out, fragment); } ...
ByteBufferはバイト単位でしか読み書きできないので、端数のビットについてはどこかに保持しておく必要がある。今回はByteFragmentというクラスを作ってそこにビット列とビット長を保持するようにしている。
移譲先のEncodeHelper/DecodeHelperの親クラスであるCharsetProcessorを実装する。
総称型を利用してエンコード/デコードのどちらでも使えるようにしておく。
package sample.charset; import java.nio.Buffer; import java.nio.charset.CoderResult; /** * CharsetEncoder/CharsetDecoderのどちらでも使えるベースクラス。 * * @param <R> 読み取り用のBufferの型 * @param <W> 書き込み用のBufferの型 */ public abstract class CharsetProcessor<R extends Buffer, W extends Buffer> { /** * 読み取り/書き込みが可能な限りの範囲で処理を行う。処理が成功したところまで * readerBuffer、writerBufferのposition、fragmentの内容を復元してから戻る。 * @param readerBuffer 読み込み用バッファ * @param writerBuffer 書き込み用バッファ * @param fragment 端数のバイト情報を保持するオブジェクト * @return CoderResultを戻す */ public final CoderResult doLoop(R readerBuffer, W writerBuffer, ByteFragment fragment) { // 読み書き処理中で使用するテンポラリのByteFragment ByteFragment committed = new ByteFragment(); readerBuffer.mark(); writerBuffer.mark(); committed.copyFrom(fragment); try { while (true) { // 一文字分の読み取り/変換/書き込みをおこなう CoderResult result = processCharacter(readerBuffer, writerBuffer, fragment); if (result != null) { // 読み取り/書き込み/コード変換などの失敗 return result; } // 結果をコミットしてループを続行する readerBuffer.mark(); writerBuffer.mark(); committed.copyFrom(fragment); } } finally { // 結果を最後にコミットした状態に戻す readerBuffer.reset(); writerBuffer.reset(); fragment.copyFrom(committed); } } /** * 一文字分の情報を読み込んで書き出す。readerBuffer/writerBufferをmarkしてはならない。 * @return 一文字分の処理に成功した場合nullを、 * それ以外の場合結果に応じて各種のCoderResultを戻す。 */ protected abstract CoderResult processCharacter(R readerBuffer, W writerBuffer, ByteFragment fragment); }
文字セットプロバイダの実装(文字の変換表)
ハフマン符号化を使うのは良いのだけど、符号化に使うテーブルを毎回データに含めるようにすると、短い場合にあまり短縮にならない。
そこで上のFizzBuzzが最短になるようなテーブルをあらかじめ作って処理する側に埋め込んでしまう。
Node/Tree/Leafという内部クラスを定義して、符号化に必要なツリーを構築する。
package sample.charset; import java.util.HashMap; import java.util.Map; public final class FizzBuzzMapping { public interface Node { } public static class Tree implements Node { public static final int LEFT = 0; public static final int RIGHT = 1; Node[] children = new Node[2]; Tree() { } Node getChild(int leftOrRight) { return children[leftOrRight]; } void setChild(int leftOrRight, Node child) { children[leftOrRight] = child; } } public static class Leaf implements Node { /** 短縮形式での符号化対象となるchar */ private char character; /** 符号のビット列をintで下詰めで保持。"0101"なら2 */ private int code; /** 符号のビット長を保持。"0101"なら4ビットなので4 */ private int codeSize; Leaf(char character, int code, int codeSize) { this.character = character; this.code = code; this.codeSize = codeSize; } public char getCharacter() { return character; } public int getCode() { return code; } public int getCodeSize() { return codeSize; } } /*
必要ならばTreeを作りながらLeafノードである符号に対するcharの情報を登録していく
*/ /** 最小コードビット長 */ public static final int MIN_CODE_SIZE; /** エスケープ用のコード */ public static final Leaf ESCAPE_NODE; /** ツリーのルートノード */ private static final Tree DECODE_ROOT = new Tree(); /** charからbitの変換はMapで保持*/ private static final Map<Character, Leaf> encodeMap = new HashMap<Character, Leaf>(); private static Leaf registerCharacter(char character, int code, int codeSize) { Node currentNode = DECODE_ROOT; for (int pos = codeSize-1; pos >= 0; pos--) { if (currentNode instanceof Leaf) { throw new IllegalArgumentException("Too long character code: " + Integer.toString(code, 16)); } int leftOrRight = (code & (1 << pos)) >> pos; Node nextNode = ((Tree) currentNode).getChild(leftOrRight); if (nextNode == null) { if (pos > 0) { // create tree node nextNode = new Tree(); ((Tree) currentNode).setChild(leftOrRight, nextNode); } else { // create leaf and break nextNode = new Leaf(character, code, codeSize); ((Tree) currentNode).setChild(leftOrRight, nextNode); encodeMap.put(character, (Leaf) nextNode); } } currentNode = nextNode; } if (currentNode instanceof Tree) { throw new IllegalArgumentException("Too short character code: " + Integer.toString(code, 16)); } return (Leaf) currentNode; } static { registerCharacter('z', 0x0, 3); // 000 registerCharacter('"', 0x2, 4); // 0010 registerCharacter('1', 0x3, 4); // 0011 registerCharacter(';', 0x4, 4); // 0100 registerCharacter('<', 0x5, 4); // 0101 registerCharacter('n', 0x6, 4); // 0110 registerCharacter(' ', 0xe, 5); // 01110 registerCharacter('%', 0xf, 5); // 01111 registerCharacter('(', 0x10, 5); // 10000 registerCharacter(')', 0x11, 5); // 10001 registerCharacter('+', 0x12, 5); // 10010 registerCharacter('0', 0x13, 5); // 10011 registerCharacter(':', 0x14, 5); // 10100 registerCharacter('?', 0x15, 5); // 10101 registerCharacter('i', 0x16, 5); // 10110 registerCharacter('t', 0x17, 5); // 10111 registerCharacter('u', 0x18, 5); // 11000 registerCharacter('.', 0x32, 6); // 110010 registerCharacter('3', 0x33, 6); // 110011 registerCharacter('5', 0x34, 6); // 110100 registerCharacter('e', 0x35, 6); // 110101 registerCharacter('m', 0x36, 6); // 110110 registerCharacter('o', 0x37, 6); // 110111 registerCharacter('r', 0x38, 6); // 111000 registerCharacter('{', 0x39, 6); // 111001 registerCharacter('}', 0x3a, 6); // 111010 registerCharacter('=', 0x76, 7); // 1110110 registerCharacter('B', 0x77, 7); // 1110111 registerCharacter('F', 0x78, 7); // 1111000 registerCharacter('S', 0x79, 7); // 1111001 registerCharacter('f', 0x7a, 7); // 1111010 registerCharacter('l', 0x7b, 7); // 1111011 registerCharacter('p', 0x7c, 7); // 1111100 registerCharacter('s', 0x7d, 7); // 1111101 registerCharacter('y', 0x7e, 7); // 1111110 ESCAPE_NODE = registerCharacter('\377', 0xff, 8); // 11111111 MIN_CODE_SIZE = 3; } /*
外部からこのテーブルを使う為のメソッドを定義する。
*/ /** charに対応する符号情報を持つLeafを戻す。未登録ならばnullを戻す */ public static final Leaf encode(Character character) { return encodeMap.get(character); } public interface BitReader { Result<Integer> readBit(); } /** 1bitずつ読んで行き、ビット列に対応する符号情報を持つLeafを戻す。 */ public static Result<Leaf> decode(BitReader bitReader) { Node current = FizzBuzzMapping.DECODE_ROOT; int codeForError = 0; while (current instanceof Tree) { Result<Integer> result = bitReader.readBit(); if (!result.succeeded) { return Result.of(result.result); } codeForError = codeForError << 1 | result.value; current = ((Tree) current).getChild(result.value); if (current == null) { throw new IllegalArgumentException("Illegal character code: " + Integer.toString(codeForError, 16)); } } return Result.of((Leaf) current); } }
読み込み中にバッファが足りなくなった場合に、値ではなくCoderResultを返せるように、Resultというクラスを定義している。
「バッファが足りない時にnullを戻す」とかにすると、沢山あると訳が分からなくなるので。
かと言って例外を正常時のロングジャンプに使うの嫌だよね。
package sample.charset; import java.nio.charset.CoderResult; /** * 各種の値の読み取りオペレーション中に、読み取りが成功した場合に値を、 * 失敗した場合にその理由を戻す為のラッパークラス。 * @param <T> 値の型 */ public class Result<T> { final boolean succeeded; final T value; final CoderResult result; private Result(T value) { this.succeeded = true; this.value = value; this.result = null; } private Result(CoderResult result) { this.succeeded = false; this.value = null; this.result = result; } static <T> Result<T> of(T value) { return new Result<T>(value); } static <T> Result<T> of(CoderResult result) { return new Result<T>(result); } }
文字セットプロバイダの実装(bit操作)
今回は1文字あたりのコードが可変長なので、ビットのシフトやマスク処理が沢山発生する。
その辺りを整理したクラスを用意しておく。
まず、端数のビットを保持する為のByteFragmentというクラスを作る。
値を持つだけではなくて、持ってる情報の範囲で数ビット単位で書くとか読むとかの処理も書いておく。
byteで持つとシフト時の正負の処理が面倒なのでなるべくintで保持する。
package sample.charset; /** * 端数ビットを保持する為のクラス。 * 読み取り時は、1バイト単位で設定し、上位ビットから読んでいく。 * 書き込み時は、上位ビットから書いて行き、1バイトに達したら値を取り出す。 */ public final class ByteFragment { /** 現在のオフセット値。何ビット目まで読んだか、または何バイト目まで書いたか。 */ int bitOffset; /** 保持しているビット列 */ int partialByte; public void copyFrom(ByteFragment other) { partialByte = other.partialByte; bitOffset = other.bitOffset; } /** 読み取り用のリセット。初期値は空で読み取ることは出来ない */ public void resetToRead() { partialByte = 0; bitOffset = 8; } /** 書き込み用のリセット。初期値は空で8bitまで書き込める。 */ public void resetToWrite() { partialByte = 0; bitOffset = 0; } /** 書き込まれている場合falseを戻す。 */ public boolean isEmpty() { return bitOffset == 0; } /** bitLength分を書き込んだ際にオーバーフローするか。 */ public boolean overflowsWhenWrite(int bitLength) { return bitOffset + bitLength >= 8; } /** ビット長bitLengthのデータbitsを書き込む。*/ public void write(int bits, int bitLength) { if (overflowsWhenWrite(bitLength)) { throw new IllegalArgumentException("too large bitLength. " + bitLength); } int newBitOffset = bitOffset + bitLength; partialByte |= bits << (8 - newBitOffset); bitOffset = newBitOffset; } /** ビット長bitLengthのデータbitsを書き込む。先頭の8bitをbyteとして戻し、残りをthisの値とする。*/ public byte writeWithOverflow(int bits, int bitLength) { if (!overflowsWhenWrite(bitLength)) { throw new IllegalArgumentException("too small bitLength. " + bitLength); } int newBitOffset = bitOffset + bitLength - 8; int overflow = partialByte | bits >> newBitOffset; partialByte = 0xff & bits << 8 - newBitOffset; bitOffset = newBitOffset; return (byte) overflow; } /** bitLength分のbitを読み取れるか。 */ public boolean canRead(int bitLength) { return bitOffset + bitLength <= 8; } /** bitLength分のbitを読み取ってintで戻す。 */ public int read(int bitLength) { if (!canRead(bitLength)) { throw new IllegalArgumentException("too large bitLength. " + bitLength); } int bits = (partialByte & 0xff >> bitOffset) >> 8 - bitOffset - bitLength; bitOffset += bitLength; return bits; } /** thisおよびnextByteからbitLength分のbitを読み取ってintで戻す。残りをthisの値とする。*/ public int read(int bitLength, int nextByte) { if (canRead(bitLength)) { throw new IllegalArgumentException("too small bitLength. " + bitLength); } int shortLength = bitOffset + bitLength - 8; int bits = (partialByte & 0xff >> bitOffset) << shortLength | nextByte >> 8 - shortLength; partialByte = nextByte; bitOffset = shortLength; return bits; } }
このByteFragmentとjava.nio.ByteBufferを組み合わせて、ビット単位での読み書きを行うユーティリクラスを作る。
ちなみに「0xff & aByte」はbyteを符号なし扱いでintにキャストしたい時に使う慣用句。
package sample.charset; import java.io.UnsupportedEncodingException; import java.nio.ByteBuffer; import java.nio.charset.CoderResult; public final class BitOperationUtils { private static final String UTF8_ENCODING = "UTF-8"; /** * 1ビット分を読み取る。 * @return 読み取りに成功した場合は読み込んだ値を、 * 読み取れなかった場合はCoderResultを含むResultオブジェクトを戻す。 */ public static Result<Integer> readBit(ByteBuffer readerBuffer, ByteFragment fragment) { if (fragment.canRead(1)) { return Result.of(fragment.read(1)); } else if (readerBuffer.hasRemaining()) { return Result.of(fragment.read(1, 0xff & readerBuffer.get())); } return Result.of(CoderResult.UNDERFLOW); } /** * 指定したバイト数分のバイト列を読み取る * @param buffer バイト列を読み込む先 * @param offset バイト列を読み込むbufferのoffset * @param length 読み込むバイト数 * @param readerBuffer ビット列読み込み用のByteBuffer * @param fragment 前回読み込んで未使用の端数バイト情報を保持するオブジェクト * @return 読み取りに成功した場合はbufferを、 * 読み取れなかった場合はCoderResultを含むResultオブジェクトを戻す。 */ public static Result<byte[]> readBytes( byte[] buffer, int offset, int length, ByteBuffer readerBuffer, ByteFragment fragment) { if (readerBuffer.remaining() < length) { return Result.of(CoderResult.UNDERFLOW); } for (int pos = 0; pos < length; pos++) { buffer[pos + offset] = (byte) fragment.read(8, 0xff & readerBuffer.get()); } return Result.of(buffer); } /** * 現在読み込み中の文字のUTF-8でのバイト数を、先頭バイトを元に計算して戻す。 * 先頭が0XXXXXXXなら1バイト、先頭が110XXXXXなら2バイト、先頭が1110XXXXなら3バイト、…… */ public static int getUTF8Length(byte firstByte) { if (firstByte >> 7 == 0) { return 1; } int length; for (length = 2; (firstByte & 1 << (7 - length)) > 0 ; length ++); return length; } /** * readerBufferからUTF-8の1文字分のビット列を読み取り、charに変換して戻す。 * @param readerBuffer ビット列読み込み用のByteBuffer * @param fragment 前回読み込んで未使用の端数バイト情報を保持するオブジェクト * @return 読み取りに成功した場合は読み込んだ一文字分のCharacterを、 * 読み取りバッファが短過ぎた場合はCoderResultを含むResultオブジェクトを戻す。 */ public static Result<Character> readUTF8Character( ByteBuffer readerBuffer, ByteFragment fragment) { // 先頭のバイトを読み取って、全体のバイト数を計算 byte[] firstByte = new byte[1]; Result<byte[]> result = BitOperationUtils.readBytes(firstByte, 0, 1, readerBuffer, fragment); if (!result.succeeded) { return Result.of(result.result); } int length = BitOperationUtils.getUTF8Length(result.value[0]); // 残りのバイトを読み出す byte[] buffer = new byte[length]; buffer[0] = firstByte[0]; result = BitOperationUtils.readBytes(buffer, 1, length - 1, readerBuffer, fragment); if (!result.succeeded) { return Result.of(result.result); } // charに変換 try { return Result.of(new String(result.value, UTF8_ENCODING).charAt(0)); } catch (UnsupportedEncodingException e) { // UTF-8に対応していないことは無いはず e.printStackTrace(); throw new IllegalStateException("Unsupported encoding: " + UTF8_ENCODING); } } /** charをUTF-8でのバイト列に変換 */ public static byte[] toBytes(char character) { try { return String.valueOf(character).getBytes(UTF8_ENCODING); } catch (UnsupportedEncodingException e) { // UTF-8に対応していないことは無いはず e.printStackTrace(); throw new IllegalStateException("Unsupported encoding: " + UTF8_ENCODING); } } }
文字セットプロバイダの実装(Encoder/DecodeおよびHelperの実装)
FizzBuzzCharsetEncoderの実装。
コンストラクタで、不明文字の為の置換バイトを定義している。今回は「0xff + "?"」を指定している。
また、implFlush()を実装し、最後に端数バイトがあった場合に1埋めして出力しきっている。
package sample.charset; import java.nio.ByteBuffer; import java.nio.CharBuffer; import java.nio.charset.Charset; import java.nio.charset.CharsetEncoder; import java.nio.charset.CoderResult; import sample.charset.FizzBuzzMapping.Leaf; class FizzBuzzCharsetEncoder extends CharsetEncoder { private static CharsetProcessor<CharBuffer, ByteBuffer> ENCODE_HELPER = new EncodeHelper(); /** 不明文字が来た場合にエスケープ文字+'?'で置き換える */ private static byte[] REPLACER = new byte[] {(byte) FizzBuzzMapping.ESCAPE_NODE.getCode(), (byte) '?'}; /** ビット書き出しの際に端数分を保持する為のByteFragment */ private ByteFragment fragment = new ByteFragment(); /** コンストラクタ */ protected FizzBuzzCharsetEncoder(Charset cs) { super(cs, 2.1F, 5.0F, REPLACER); implReset(); } /** encodeLoop()の実装。EncodeHelperに委譲 */ @Override protected CoderResult encodeLoop(CharBuffer in, ByteBuffer out) { return ENCODE_HELPER.doLoop(in, out, fragment); } /** 状態をリセット。このクラスはfragmentしか状態が無いのでfragmentを書き出し用としてリセット。*/ protected void implReset() { fragment.resetToWrite(); } /** 最後に書き出しが必要な場合に実装。端数のbitがあれば1詰めで1バイトにして出力 */ protected CoderResult implFlush(ByteBuffer out) { if (fragment.isEmpty()) { return CoderResult.UNDERFLOW; //何もせずUNDERFLOWを戻す } // 追加の出力が必要 if (!out.hasRemaining()) { return CoderResult.OVERFLOW; } out.put(fragment.writeWithOverflow(0xff, 8)); return CoderResult.UNDERFLOW; //書き込んだ後UNDERFLOWを戻す。 } /*
EncodeHelperの実装。
読み込んだcharが短縮用のテーブルにある場合はその符号ビット列を、
無い場合はエスケープ用コード+UTF-8を出力している。
*/ /** * エンコード用のAbstractCharsetProcessorの実装。 */ private static class EncodeHelper extends CharsetProcessor<CharBuffer, ByteBuffer> { /** * CharBufferから一文字分のcharを読み取り、エンコードしてByteBufferに書き出す。 * エンコードしたビット列がfragmentに収まった場合、ByteBufferへの書き出しはおこなわない。 */ @Override protected CoderResult processCharacter( CharBuffer readerBuffer, ByteBuffer writerBuffer, ByteFragment fragment) { // 一文字分を読み取れるか確認 if (!readerBuffer.hasRemaining()) { return CoderResult.UNDERFLOW; } // 一文字分を読み取り char character = readerBuffer.get(); // 短縮コードとしてエンコードできるかを確認し、可能なら書き込んで戻る Leaf characterNode = FizzBuzzMapping.encode(character); if (characterNode != null) { return writeCode(characterNode, writerBuffer, fragment); } // エスケープ(0xff) + UTF-8でのバイト列表現として書き込む byte[] bytes = BitOperationUtils.toBytes(character); return writeCode(FizzBuzzMapping.ESCAPE_NODE, writerBuffer, fragment) == null ? writeBytes(bytes, writerBuffer, fragment) : CoderResult.OVERFLOW; } /** characterLeafに含まれるコードを書き出す。 */ private CoderResult writeCode(Leaf characterLeaf, ByteBuffer writerBuffer, ByteFragment fragment) { if (!fragment.overflowsWhenWrite(characterLeaf.getCodeSize())) { fragment.write(characterLeaf.getCode(), characterLeaf.getCodeSize()); } else { if (! writerBuffer.hasRemaining()) { return CoderResult.OVERFLOW; } writerBuffer.put(fragment.writeWithOverflow(characterLeaf.getCode(), characterLeaf.getCodeSize())); } return null; } /** bytesに含まれるバイト列をを書き出す。 */ private CoderResult writeBytes(byte[] bytes, ByteBuffer writerBuffer, ByteFragment fragment) { if (writerBuffer.remaining() < bytes.length) { return CoderResult.OVERFLOW; } for (int pos = 0; pos < bytes.length; pos++) { writerBuffer.put(fragment.writeWithOverflow(0xff & bytes[pos], 8)); } return null; } } }
FizzBuzzCharsetDecoderの実装。
コンストラクタで、1バイトあたりの最大文字数を設定している。これが短いとオーバーフローのエラーで落ちる。*3
package sample.charset; import java.nio.ByteBuffer; import java.nio.CharBuffer; import java.nio.charset.Charset; import java.nio.charset.CharsetDecoder; import java.nio.charset.CoderResult; import sample.charset.FizzBuzzMapping.BitReader; import sample.charset.FizzBuzzMapping.Leaf; class FizzBuzzCharsetDecoder extends CharsetDecoder { private static CharsetProcessor<ByteBuffer, CharBuffer> DECODE_HELPER = new DecodeHelper(); private static int MAX_CHARS_PER_BYTE = (int) Math.ceil(8 / FizzBuzzMapping.MIN_CODE_SIZE); /** ビット読み出しの際に端数分を保持する為のByteFragment */ private ByteFragment fragment = new ByteFragment(); /** コンストラクタ */ protected FizzBuzzCharsetDecoder(Charset cs) { super(cs, 1.0F, MAX_CHARS_PER_BYTE); implReset(); } /** decodeLoop()の実装。DecodeHelperに委譲 */ @Override protected CoderResult decodeLoop(ByteBuffer in, CharBuffer out) { return DECODE_HELPER.doLoop(in, out, fragment); } /** 状態をリセット。このクラスはfragmentしか状態が無いのでfragmentを読み取り用としてリセット。*/ protected void implReset() { fragment.resetToRead(); } /*
DecodeHelperの実装。
読み込んだbit列に対応するcharが短縮用のテーブルにある場合はそのcharを、
エスケープ用コードの場合はそれに続くUTF-8の文字を読み出す。UTF-8の文字が何バイトになるかは先頭のバイトのビットパターンを見て確定する。
このあたり参照
*/ /** * デコード用のAbstractCharsetProcessorの実装。 */ private static class DecodeHelper extends CharsetProcessor<ByteBuffer, CharBuffer> { /** * ByteBufferから一文字分のbit列を読み取り、エンコードしてCharBufferに書き出す。 * fragmentに残っている分で一文字分に足りた場合はByteBufferからの読み取りはおこなわない。 */ @Override protected CoderResult processCharacter( ByteBuffer readerBuffer, CharBuffer writerBuffer, ByteFragment fragment) { // 一文字分を読み取り Result<Character> result = readCharacter(readerBuffer, fragment); if (! result.succeeded) { return result.result; } // 一文字分を書き込めるか確認 if (writerBuffer.remaining() < 1) { return CoderResult.OVERFLOW; } // 一文字分を書き込む writerBuffer.put(result.value); return null; // 成功 } // 一文字分のビット列を読み込んでデコードする private static Result<Character> readCharacter( final ByteBuffer readerBuffer, final ByteFragment fragment) { // 一ビットずつ読みながらデコード Result<Leaf> result = FizzBuzzMapping.decode(new BitReader() { public Result<Integer> readBit() { return BitOperationUtils.readBit(readerBuffer, fragment); } }); if (!result.succeeded) { // 読み取りバッファが足りないなど return Result.of(result.result); } if (result.value == FizzBuzzMapping.ESCAPE_NODE) { // エスケープ用のコード(0xff)なら、UTF-8一文字分を読み込んで戻す。 return BitOperationUtils.readUTF8Character(readerBuffer, fragment); } // 短縮コード形式なら対応するcharを戻す return Result.of(result.value.getCharacter()); } } }
SPIファイルの用意
META-INF/servicesというディレクトリを作って、java.nio.charset.spi.CharsetProviderというファイルを置く。
中身は、CharsetProviderの実装クラスのFQCNを書く。
META-INF/services/java.nio.charset.spi.CharsetProvider:
# NIO charset SPI extended charset provider sample.charset.FizzBuzzCharsetProvider
これを上記のソースコードのコンパイル結果と一緒にjarにする。
一応jar化したのとFizzBuzz文字コード版のFizzBuzzクラスのソースを貼っておくよ。
fizzbuzzcharsets.jar
fizzbuzzcharsets-src.jar
z.java
