Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 

2016年07月22日

[]Unicode の文字数カウント

一年半前に C++11 に慣れるために GNU coreutils の wc (1) コマンドを書き直したときに、 wc (1) に合わせて文字数をワイド文字の個数としていました。 ところで、 LC_CTYPE が ja_JP.UTF8 のとき、 UTF-8デコードしたコード・ポイント一つずつがそのままワイド文字に変換されるだけです。 そのため、 複数のコード・ポイント列が一文字になる合成文字や異字体漢字が入力に含まれている場合、 出力は文字の個数ではなくなります。 ここは、 やはり文字数を表示するように改善したいものです。

合成文字を一文字に数えるのは簡単で、 結合クラスがゼロでないコード・ポイントを無視すればことたります。 異字体漢字も同様で、 異字体セレクタを無視すれば良いだけです。 他に、 無視するべきは、 既に使ってはいけないことになっている幽霊コード・ポイントの言語タグと、 UTF-8 では出現してはならないサロゲートも無視することにします。 これで、 だいたい表示される見た目の文字数に近い個数が文字数として出力されることになります。 扱いに迷うのは書式文字で、 左右上下の方向指定コード・ポイントやグリフ結合指定コード・ポイントは無視した方が良いのかもしれないと考えつつも、 今回は文字として扱って個数にいれています。

namespace ucd {

int canonincal_combining_class (char32_t codepoint);
bool is_surrogate (char32_t codepoint);
bool is_variation_selector (char32_t codepoint);
bool is_language_tag (char32_t codepoint);

}//namespace ucd

static inline bool
is_character_base_code (char32_t codepoint)
{
    return ! ucd::is_surrogate (codepoint)
        && ! ucd::is_variation_selector (codepoint)
        && ! ucd::is_language_tag (codepoint)
        && ucd::canonincal_combining_class (codepoint) == 0;
}

結合クラスには UnicodeData Canonical Combining Class のダブル配列トライ を使います。 他は、 コード範囲に含まれているかどうか調べるようにします。

namespace ucd {

bool
is_surrogate (char32_t codepoint)
{
    return 0x00d800L <= codepoint && codepoint <= 0x00dfffL;
}

bool
is_variation_selector (char32_t codepoint)
{
    return (0x180bL <= codepoint && codepoint <= 0x180dL)
        || (0xfe00L <= codepoint && codepoint <= 0xfe0fL)
        || (0xe0100L <= codepoint && codepoint <= 0xe01efL);
}

bool
is_language_tag (char32_t codepoint)
{
    return 0xe0001L <= codepoint && codepoint <= 0xe007fL;
}

}//namespace ucd

これで文字を数えるように修正することができます。 以前はワイド文字列の長さを足していたのを止めて、 文字の個数を数えるのに使うコード・ポイントを数えるようにします。

void wordcount_counter::countline (std::string& octets)
{
    auto line = t42::decode (octets);
    bc += octets.size ();
    bt += octets.size ();
    if (! octets.empty () && octets[octets.size () - 1] == '\n') {
        lc++;
        lt++;
    }
    enum {OUTWORD, INWORD} state = OUTWORD;
    std::locale loc (std::locale::classic (), "", std::locale::ctype);
    for (auto c : line) {
        if (is_character_base_code (c)) {
            cc++;
            ct++;
        }
        if (std::isspace (c, loc)) {
            state = OUTWORD;
        }
        else if (state == OUTWORD) {
            state = INWORD;
            wc++;
            wt++;
        }
    }
}

2016年07月12日

[][]UnicodeData Canonical Combining Class のダブル配列トライ

Unicode の合成文字は、 UnicodeData.txt の第 3 欄 Canonical Cobining Class の数値がゼロでないものを抽出します。 以前は狭い範囲で収まっていて単純なテーブル参照で済んでいたのですけど、 広い範囲にばらけながら増える一方なので、 ダブル配列のトライを作ることにしました。

コードポイントの下 3 バイトを使い、 それぞれのバイトでトライ木の枝分かれをしていくようにします。

int
canonincal_combining_class (char32_t codepoint)
{
    static const short base[] = {
        // Perl で生成
    };
    static const short check[] = {
        // Perl で生成
    };
    int const ncheck = sizeof (check) / sizeof (check[0]);
    int const k0 = (codepoint >> 16) & 0xff;
    int const k1 = (codepoint >>  8) & 0xff;
    int const k2 = (codepoint      ) & 0xff;

    int state = 1;
    int next_state = base[state] + k0;
    if (0 < next_state && next_state < ncheck && check[next_state] == state) {
        state = next_state;
        next_state = base[state] + k1;
        if (0 < next_state && next_state < ncheck && check[next_state] == state) {
            state = next_state;
            next_state = base[state] + k2;
            if (0 < next_state && next_state < ncheck && check[next_state] == state) {
                return base[next_state];
            }
        }
    }
    return 0;
}

ダブル配列は Perl で生成します。

#/usr/bin/env perl
use strict;
use warnings;
use List::Util qw(any shuffle);

my %trie;
#@<UnicodeData.txt を読んで、第 0 欄をキー、第 3 欄を値とするトライ木を作ります@>

my @base = (0);
my @check = (-1, -1);
#@<トライ木からダブル配列を作ります@>

print "static const short base[] = {\n    ";
for my $i (0 .. $#check) {
    printf "%4d,%s", defined $base[$i] ? $base[$i] : 0,
        $i % 10 < 9 ? " " : "\n    ";
}
print "\n};\nstatic const short check[] = {\n    ";
for my $i (0 .. $#check) {
    printf "%4d,%s", defined $check[$i] ? $check[$i] : 0,
        $i % 10 < 9 ? " " : "\n    ";
}
print "\n};\n";

Unicode 8.0 での対象コードポイントは 751 個にすぎないので、 トライ木を作って、 それから静的にダブル配列を作ることにします。

#@<UnicodeData.txt を読んで、第 0 欄をキー、第 3 欄を値とするトライ木を作ります@>=
while (<>) {
    my @f = split /;/, $_, -1;
    next if $f[3] == 0;     # Start コードポイントは対象外
    my $codepoint = hex($f[0]);
    my $k0 = ($codepoint >> 16) & 0xff;
    my $k1 = ($codepoint >>  8) & 0xff;
    my $k2 = ($codepoint      ) & 0xff;
    $trie{$k0}{$k1}{$k2} = $f[3];
}

初期状態を 1 として、 ダブル配列を作ります。 トライ木からダブル配列を作るには、 分岐の節のキーをストアップし、 それを check 配列の隙間にはめ込んでいきます。 深さ優先と幅優先の両方で動かしてみて、 どちらが小さなダブル配列になるか比較してみたのですが、 優位差は生じなかったので、 深さ優先の方を書いておきます。

#@<トライ木からダブル配列を作ります@>=
my $s0 = 1;
my @key0 = sort { $a <=> $b } keys %trie;
$base[$s0] = 2 - $key0[0];
for my $k0 (@key0) {
    $check[$base[$s0] + $k0] = $s0;
}
for my $k0 (@key0) {
    my $s1 = $base[$s0] + $k0;
    my @key1 = sort { $a <=> $b } keys %{$trie{$k0}};
    $base[$s1] = 1 - $key1[0];
    while (any { defined $check[$base[$s1] + $_] } @key1) {
        ++$base[$s1];
    }
    for my $k1 (@key1) {
        $check[$base[$s1] + $k1] = $s1;
    }
    for my $k1 (shuffle @key1) {
        my $s2 = $base[$s1] + $k1;
        my @key2 = sort { $a <=> $b } keys %{$trie{$k0}{$k1}};
        $base[$s2] = 1 - $key2[0];
        while (any { defined $check[$base[$s2] + $_] } @key2) {
            ++$base[$s2];
        }
        for my $k2 (@key2) {
            $base[$base[$s2] + $k2] = $trie{$k0}{$k1}{$k2};
            $check[$base[$s2] + $k2] = $s2;
        }
    }
}

key1 をシャッフルして、 割り当て順をランダムに変えています。 これで、 なんどかスクリプトを走らせて、 一番行数が少ないものを選んで利用しています。 1 行 10 個ずつで折り返して、 base と check あわせて少ない方は 2100 行前後になります。

2016年07月08日

[]Unicode East Asian Width さらに

Unicode East Asian Width 再び 」では、 コードポイント範囲を二分探索して幅を求めていました。 コードポイント範囲のテーブルのメンテナンスのやりやすさと、 テーブル・サイズを小さくできるというメリットがある反面、 ワースト・ケースでは 8 回の繰り返しがかかります。

そこで、 テーブル・サイズを増やして、 どのコード・ポイントに対しても、4 回以下の条件判定で幅を求めるようにしてみました。 先頭 512 ブロック分の幅を表で求めます。 表は 2 段構成になっていて、 まずブロック単位の表を使います。 この表は幅欄とブロック付け替え先欄の 2 つからなり、 ブロック内がすべて同じ幅のときは幅欄から幅が求まります。 異なる幅が混在しているときは、 ブロック付け替え先欄のブロック番号へとコードポイントのブロック番号を入れ替えます。 続いて、 入れ替えたコードポイントで 2 段目の表を引いて幅を求めます。

2016 年 7 月 9 日修正 当初は 3 段の表を使って表のバイトサイズを減らしていましたが、 スピード優先で 2 段に変更しました。

// return 2: 全角 "F" "W", 3: Ambigious "A", 1: 半角
int
east_asian_width (std::uint32_t code)
{
    std::uint8_t const blockdir[] = {
//@<ブロック索引@>
    };
    std::uint32_t const bitmap[] = {
//@<2 ビット単位のビットマップ表@>
    };
    if (code < 0x80) {
        return 1;                   // ASCII7 の幅は 1 
    }
    else if (code < 0x020000) {     // 先頭 512 ブロック
        std::uint32_t const = blockdir[code >> 8];
        if (block & 3) {
            return block;           // 256 コードポイントがすべて同じ幅
        }
        code = (block << 6) + (code & 0xff);                   // ブロック番号を入れ替えます
        return (bitmap[code >> 4] >> ((code & 15) << 1)) & 3;  // ビットマップ表を引きます
    }
    else if (code < 0x040000) {
        return 2;
    }
    else if (code < 0x0e0100) {
        return 1;
    }
    else {
        return 3;
    }
}

1段目の表は、 ブロック索引で、 512 バイトの大きさです。 1 バイトの下位 2 ビットが幅欄で、 1 から 3 の値のときはブロック内の 256 個のすべてのコードポイントが同じ幅をもっています。

   MSB       LSB
    |000000|01| → 全部半角 1

    |000000|10| → 全部全角 2

    |000000|11| → 全部曖昧(A) 3

幅欄がゼロのときは、 異なる幅が混在していることを表します。 混在の場合、 上位 6 ビットにコードポイントのブロック番号の入れ替え先番号が記入してあります。

   MSB                                LSB
    |000000000000000|yyyyyyyyy|xxxxxxxx|  入れ替え前
                          ↓        |
                       |zzzzzz|00|  |    ブロック表
                          ↓        ↓
    |000000000000000|000zzzzzz|xxxxxxxx|  入れ替え後

512 ブロック中、 幅混在ブロックは 29 個しかありません。 そのため、 ブロック番号を入れ替えて、 29 個のブロックを先頭から詰めた表を引くことで、 2 段目の表のサイズを小さくしています。

//@<ブロック索引@>=
        0x00, 0x04, 0x08, 0x0c, 0x10, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x14, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x18, 0x1c, 0x20, 0x24,
        0x28, 0x2c, 0x30, 0x34, 0x01, 0x01, 0x01, 0x38, 0x01, 0x01, 0x3c, 0x40,
        0x44, 0x48, 0x4c, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x50, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x54, 0x01, 0x01, 0x01,
        0x01, 0x58, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
        0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x5c,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x03, 0x03, 0x03, 0x03,
        0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
        0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x02, 0x02, 0x01,
        0x01, 0x01, 0x60, 0x64, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x68, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x6c, 0x70, 0x01, 0x01, 0x01, 0x01, 0x01,
        0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,

2 段目の表は、 異なる幅が混在している 29 個を選んで先頭から詰め直し、 それぞれのコードポイントの幅を 2 ビットでパックしています。 幅は LSB から MSB へと並べています。

//@<2 ビット単位のビットマップ表@>=
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x7d77d75d, 0xff7ff7ff,
        0x55557555, 0xf557d557, 0x5f7f755f, 0x777fd5f7, 0x5555555d, 0x55d555dd,
        0x55d5f555, 0xd55755fd, 0x5dff577f, 0x555555f5, 0x55d5f555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x75555555, 0x57777777,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x5555555d, 0x5555555d, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x5dfdd755, 0xddff5557, 0x55555555, 0x55555555,
        0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff,
        0xffffffff, 0x55555555, 0x55555555, 0xfffffffd, 0x555fffdf, 0xfffffffd,
        0x555fffdf, 0x55555555, 0x55555555, 0x55555555, 0x5555555d, 0xffffffff,
        0xffffffff, 0xffffffff, 0xffffffff, 0x5555555d, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x5f5f7fd7, 0x5555ff7f, 0x75d55df7, 0x55555555, 0x55555555,
        0x55555555, 0xd5555755, 0x555557fd, 0x55555555, 0x57555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x555d5dd5, 0x555575d5,
        0x55d5757d, 0x55555555, 0x55555555, 0x7fd557d5, 0x55ffffff, 0x555fffff,
        0x555d5555, 0x555fffff, 0x55555555, 0x555f5555, 0x55555555, 0x55555775,
        0x5555d555, 0x55555555, 0xd5d7d5f7, 0xfd755d5d, 0x77ffddd7, 0x5f55ff55,
        0x57575555, 0x55555575, 0xf5f5ff5f, 0x55555555, 0x5555f5f5, 0x555d5d55,
        0x55555d55, 0xd5555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555575, 0x55695555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0xffffffff, 0xffffffff,
        0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff,
        0xffdfffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff,
        0x55ffffff, 0xffffffff, 0xffffffff, 0x555555ff, 0xffffffff, 0x55555ff5,
        0x555fffdf, 0x5f55f5f5, 0xf5d7f55f, 0x5555555f, 0xd5555ff5, 0x55555555,
        0xf55d7d55, 0x77555f55, 0x55555555, 0x55555555, 0x55555577, 0x55555555,
        0xdf7fdfdf, 0x55555555, 0x55555555, 0xf5555555, 0x55555555, 0xf5555555,
        0xdfffff55, 0xffffffff, 0xffff55df, 0xffffffff, 0x55555555, 0x55555555,
        0x55555555, 0x5d555555, 0x55555555, 0x5555d555, 0x55555555, 0xfffff555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x555ffd55, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0xaaaaaaaa, 0xaa9aaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0x555555aa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0x55555aaa,
        0x55555555, 0x55aaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0x6aaaaaaa,
        0xaaaaaaa9, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaa96aaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaa955, 0xaaaaaaaa, 0x5aaaaaaa, 0xaaaaaaa9, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0x6aaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0x556aaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0x555555aa, 0xaaaaaaaa, 0xaaaaaaaa, 0x6aaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0xffffaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0x6aaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0x56aaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0x55556aaa, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0xaaaaaaaa, 0x56aaaaaa,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa,
        0x555555aa, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0xffffffff, 0x555aaaaa, 0x55555555, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaa6a,
        0x55aa6aaa, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0xaaaaaaa9, 0xaaaaaaaa,
        0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0xaaaaaaaa, 0x55555556, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55556aaa, 0x5d555555, 0x5555555a, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x557fffff, 0xffffffff, 0x5fffffff, 0xffffffff, 0xffffffff, 0xffffffff,
        0x555fffff, 0xffffffff, 0xffffffff, 0x557fffff, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x5555556a, 0xaaaaaaaa,
        0xaaaaaaaa, 0x556aaaaa, 0x5556aaaa, 0x5555555a, 0x55555555, 0x55555555,
        0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555, 0x55555555,
        0x55555555, 0x55555555,