29ビット以上のint値にも対応できるようにSimple9を調整
Simple-9について解説 - tsubosakaの日記
http://ameblo.jp/th0083/entry-10483740192.html
Simple9は、整数列を高速に圧縮するアルゴリズムです。32bitのint値を上位4bitと下位28bitに分けて、下位28bitにデータをできるだけ多く詰め込み、上位4bitで詰め込みのパターンを表現します。パターンは全部で9種類あります。
| 上位4bit | パターン |
|---|---|
| 0000 | 1bit x 28 |
| 0001 | 2bit x 14 |
| 0010 | 3bit x 9 |
| 0011 | 4bit x 7 |
| 0100 | 5bit x 5 |
| 0101 | 7bit x 4 |
| 0110 | 9bit x 3 |
| 0111 | 14bit x 2 |
| 1000 | 28bit x 1 |
ただしこのレイアウトでは、圧縮対象の整数列の中に29bit以上の数値が入っている場合に対応できません。そこで、詰め込み方を少し変更してみました。
| 上位4bit | パターン |
|---|---|
| 0000 | 1bit x 28 |
| 0001 | 2bit x 14 |
| 0010 | 3bit x 9 |
| 0011 | 4bit x 7 |
| 0100 | 5bit x 5 |
| 0101 | 7bit x 4 |
| 0110 | 9bit x 3 |
| 0111 | 14bit x 2 |
| 10XX | 30bit x 1（XXのビットも使って30bitを表現する） |
| 1100 | ここでの残りビットは捨て、次の位置に32bit x 1を置く |
この表のように、上位4bitのうち2bitを使うことで30bitまでは詰め込めるようにしてみました。
以下、プログラムです。パフォーマンス重視のためTroveを使い、全部のパターンをハードコーディングしました。
import gnu.trove.TIntArrayList; public class SafeSimple9Codec { public int[] encode(int[] array) { // 再割り当てを避けるため初期サイズを大きめに取る TIntArrayList result = new TIntArrayList(array.length); int len = array.length; int i = 0, n = 0, code = 0, v = 0; while (i < len) { // 1bit x 28 for (n = 0, code = 0; n < 28 && i + n < len && ((v = array[i + n]) & ~0x1) == 0; n++) { code = (code << 1) | v; } if (n == 28) { result.add(0x00000000 | code); i += n; continue; } // 2bit x 14 for (n = 0, code = 0; n < 14 && i + n < len && ((v = array[i + n]) & ~0x3) == 0; n++) { code = (code << 2) | v; } if (n == 14) { result.add(0x10000000 | code); i += n; continue; } // 3bit x 9 for (n = 0, code = 0; n < 9 && i + n < len && ((v = array[i + n]) & ~0x7) == 0; n++) { code = (code << 3) | v; } if (n == 9) { result.add(0x20000000 | code); i += n; continue; } // 4bit x 7 for (n = 0, code = 0; n < 7 && i + n < len && ((v = array[i + n]) & ~0xf) == 0; n++) { code = (code << 4) | v; } if (n == 7) { result.add(0x30000000 | code); i += n; continue; } // 5bit x 5 for (n = 0, code = 0; n < 5 && i + n < len && ((v = array[i + n]) & ~0x1f) == 0; n++) { code = (code << 5) | v; } if (n == 5) { result.add(0x40000000 | code); i += n; continue; } // 7bit x 4 for (n = 0, code = 0; n < 4 && i + n < len && ((v = array[i + n]) & ~0x7f) == 0; n++) { code = (code << 7) | v; } if (n == 4) { result.add(0x50000000 | code); i += n; continue; } // 9bit x 3 for (n = 0, code = 0; n < 3 && i + n < len && ((v = array[i + n]) & ~0x1ff) == 0; n++) { code = (code << 9) | v; } if (n == 3) { result.add(0x60000000 | code); i += n; continue; } // 14bit x 2 for (n = 0, code = 0; n < 2 && i + n < len && ((v = array[i + n]) & ~0x3fff) == 0; n++) { code = (code << 14) | v; } if (n == 2) { result.add(0x70000000 | code); i += n; continue; } // 30bit x 1 if (((v = array[i]) & ~0x3fffffff) == 0) { result.add(0x80000000 | v); i++; continue; } // (over 30 bit) result.add(0xc0000000); result.add(v); i++; } return result.toNativeArray(); } public int[] decode(int[] array) { // 再割り当てを避けるため初期サイズを大きめに取る TIntArrayList result = new TIntArrayList(array.length); int len = array.length; for (int i = 0; i < len; i++) { int v = array[i]; int selector = (v >> 28) & 0xf; switch (selector) { case 0x0: // 1bit x 28 result.add((v >> 27) & 0x1); result.add((v >> 26) & 0x1); result.add((v >> 25) & 0x1); result.add((v >> 24) & 0x1); result.add((v >> 23) & 0x1); result.add((v >> 22) & 0x1); result.add((v >> 21) & 0x1); result.add((v >> 20) & 0x1); result.add((v >> 19) & 0x1); result.add((v >> 18) & 0x1); result.add((v >> 17) & 0x1); result.add((v >> 16) & 0x1); result.add((v >> 15) & 0x1); result.add((v >> 14) & 0x1); result.add((v >> 13) & 0x1); result.add((v >> 12) & 0x1); result.add((v >> 11) & 0x1); result.add((v >> 10) & 0x1); result.add((v >> 9) & 0x1); result.add((v >> 8) & 0x1); result.add((v >> 7) & 0x1); result.add((v >> 6) & 0x1); result.add((v >> 5) & 0x1); result.add((v >> 4) & 0x1); result.add((v >> 3) & 0x1); result.add((v >> 2) & 0x1); result.add((v >> 1) & 0x1); result.add(v & 0x1); break; case 0x1: // 2bit x 14 result.add((v >> 26) & 0x3); result.add((v >> 24) & 0x3); result.add((v >> 22) & 0x3); result.add((v >> 20) & 0x3); result.add((v >> 18) & 0x3); result.add((v >> 16) & 0x3); result.add((v >> 14) & 0x3); result.add((v >> 12) & 0x3); result.add((v >> 10) & 0x3); result.add((v >> 8) & 0x3); result.add((v >> 6) & 0x3); result.add((v >> 4) & 0x3); result.add((v >> 2) & 0x3); result.add(v & 0x3); break; case 0x2: // 3bit x 9 result.add((v >> 24) & 0x7); result.add((v >> 21) & 0x7); result.add((v >> 18) & 0x7); result.add((v >> 15) & 0x7); result.add((v >> 12) & 0x7); result.add((v >> 9) & 0x7); result.add((v >> 6) & 0x7); result.add((v >> 3) & 0x7); result.add(v & 0x7); break; case 0x3: // 4bit x 7 result.add((v >> 24) & 0xf); result.add((v >> 20) & 0xf); result.add((v >> 16) & 0xf); result.add((v >> 12) & 0xf); result.add((v >> 8) & 0xf); result.add((v >> 4) & 0xf); result.add(v & 0xf); break; case 0x4: // 5bit x 5 result.add((v >> 20) & 0x1f); result.add((v >> 15) & 0x1f); result.add((v >> 10) & 0x1f); result.add((v >> 5) & 0x1f); result.add(v & 0x1f); break; case 0x5: // 7bit x 4 result.add((v >> 21) & 0x7f); result.add((v >> 14) & 0x7f); result.add((v >> 7) & 0x7f); result.add(v & 0x7f); break; case 0x6: // 9bit x 3 result.add((v >> 18) & 0x1ff); result.add((v >> 9) & 0x1ff); result.add(v & 0x1ff); break; case 0x7: // 14bit x 2 result.add((v >> 14) & 0x3fff); result.add(v & 0x3fff); break; case 0xc: // (over 30bit) result.add(array[i + 1]); i++; break; default: // 30bit x 1 result.add(v & 0x3fffffff); break; } } return result.toNativeArray(); } }
