branches/mty-makai/mty.c

/***********************************************************************
 *
 *      file: mty.cpp
 *
 *      まあ、待て屋。
 *
 *      $Id$
 *
 */

#define DEBUG 0
#define USE_DT 1

#ifndef DEBUG
#define NDEBUG
#endif

#ifdef __MSVCRT__
#include <windows.h>
#include <sys/timeb.h>
#else
#include <sys/mman.h>
#endif

#include <sys/time.h>
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "crypt64.h"
#include "dt4.h"

/* 鍵転置 PC1 */
static int const tr_pc1[8][7] =
{
  { 8, 16, 24, 56, 52, 44, 36},
  { 7, 15, 23, 55, 51, 43, 35},
  { 6, 14, 22, 54, 50, 42, 34},
  { 5, 13, 21, 53, 49, 41, 33},
  { 4, 12, 20, 28, 48, 40, 32},
  { 3, 11, 19, 27, 47, 39, 31},
  { 2, 10, 18, 26, 46, 38, 30},
  { 1,  9, 17, 25, 45, 37, 29},
};

/* LR最終転置 */
static int const tr_fp[64 + 2] =
{
  39,  7, 47, 15, 55, 23, 63, 31,
  38,  6, 46, 14, 54, 22, 62, 30,
  37,  5, 45, 13, 53, 21, 61, 29,
  36,  4, 44, 12, 52, 20, 60, 28,
  35,  3, 43, 11, 51, 19, 59, 27,
  34,  2, 42, 10, 50, 18, 58, 26,
  33,  1, 41,  9, 49, 17, 57, 25,
  32,  0, 40,  8, 48, 16, 56, 24,
  64, 64,
};

/* 1ビット分 */
struct SLICE
{
  unsigned long a[2];
};

/* crypt64() が喰うパラメータ */
struct PARAM
{
  struct SLICE lr[2][32];
  struct SLICE t[32];
  struct SLICE hit[10][64];
  struct SLICE hiti[10][26];
};

/* 鍵はLR と、そのコピーが必要 */
struct KEY
{
  struct SLICE k[2][2][28];
};

/* 漢字クラス表 */
unsigned char cp932[0x10000] = {
#include "cp932.inc"
};

/* 鍵文字列 */
unsigned char key[8 + 8];
unsigned char okey[8 + 8];

/* 鍵クラス */
struct
{
  unsigned cls;
  unsigned map[256];
} kcls[8 + 8];

#define KCLS_AN 1
#define KCLS_KA 2
#define KCLS_K1 4
#define KCLS_DT0 64
#define KCLS_DT1 128
#define KCLS_K2 256

#if USE_DT
/* 鍵キメ用辞書インデクス */
struct DT *kd[8 + 8];

/* 辞書インデクス */
struct DT *dtidx[0x100 + 1];
#endif

/* 指定されたクラスと入っているキーから、classify を行う */
void
key_make_map(int n)
{
  int i, j;
  unsigned c = kcls[n].map[key[n]];

  if (3 <= n && n < 7 && kd[n - 3])
        {
          /* 辞書のケツの文字。後ろにナニヤラキャラクタが来る */
          c = kd[n - 3]->c[0];
          if ((0x81 <= c && c <= 0x9F)
                  || (0xE0 <= c && c <= 0xFC))
                c = KCLS_K2;
          else
                c = (cp932[256 * key[n]]
                         | cp932[256 * (key[n] ^ 0x80)]);
#if DEBUG>=1
          printf("*n=%d, key=%02X, cls=%04X\n",
                         n,
                         key[n],
                         c);
#endif
        }
  else if (2 <= n && n < 6 && kd[n - 2])
        {
          return;
        }
  else if (1 <= n && n < 5 && kd[n - 1])
        {
          return;
        }
  else if (1 <= n && n < 5 && !kd[n - 1]
                   //&& (c & KCLS_K2)
                   && (c & KCLS_DT1))
        {
          /* 漢字2文字を拾っていきまつ */
#if DEBUG>=1
          printf("(%d)%02X %02X(%02X:%02X:%02X:%02X)\n",
                         n, key[n - 1], key[n],
                         cp932[(256 * key[n - 1] + key[n])],
                         cp932[(256 * key[n - 1] + key[n]) ^ 0x0080],
                         cp932[(256 * key[n - 1] + key[n]) ^ 0x8000],
                         cp932[(256 * key[n - 1] + key[n]) ^ 0x8080]);
#endif
          if (n != 1 && n != 2
                  && (cp932[(256 * key[n - 1] + key[n]) ^ 0x0080] & KCLS_DT1))
                key[n] ^= 0x80;
          else if (n != 2 && n != 3
                           && (cp932[(256 * key[n - 1] + key[n]) ^ 0x8000] & KCLS_DT1))
                key[n - 1] ^= 0x80;
          else if (n > 3 && (cp932[(256 * key[n - 1] + key[n]) ^ 0x8080] & KCLS_DT1))
                key[n - 1] ^= 0x80, key[n] ^= 0x80;
          if (cp932[256 * key[n - 1] + key[n]] & KCLS_DT1)
                {
                  for (kd[n - 1] = dtidx[key[n - 1]];
                           kd[n - 1]->c[1] != key[n];
                           kd[n - 1]++)
                        assert(kd[n - 1]->c[0] == key[n - 1]);
#if DEBUG>=1
                  printf("(%02X%02X:%02X%02X)%c%c%c%c\n",
                                 kd[n - 1]->c[0],
                                 kd[n - 1]->c[1],
                                 kd[n - 1]->c[2],
                                 kd[n - 1]->c[3],
                                 kd[n - 1]->c[0],
                                 kd[n - 1]->c[1],
                                 kd[n - 1]->c[2],
                                 kd[n - 1]->c[3]);
#endif
                  return;
                }
        }
  else if (n < 4 && (c & KCLS_DT0) && kd[n] == NULL)
        {
          /* カタカナ埋め込みいきます */
          assert(kd[n] == NULL);
#if DEBUG>=1
          printf("n=%d, key=%02X\n", n, key[n]);
#endif
          kd[n] = dtidx[key[n]];
          if (!kd[n]
                  && !(n == 1 || n == 2)
                  && dtidx[key[n] ^ 0x80])
                {
                  key[n] ^= 0x80;
                  kd[n] = dtidx[key[n]];
                }
          if (kd[n])
                return;
        }
  else
        {
          kd[n] = NULL;
        }

  /* 最後の部分は class map を生成する必要ナシ */
  if (n >= 6)
        return;

  for (i = 0; i < 256; i++)
        {
          unsigned bs = 0, bm = 0;
#if 1
          if (c & KCLS_K1)
                {
                  if (cp932[256 * key[n] + i] & KCLS_K1)
                        bm |= KCLS_K2 | (cp932[256 * key[n] + i] & KCLS_DT1);
                  if (cp932[256 * (key[n] ^ 0x80) + i] & KCLS_K1)
                        bm |= KCLS_K2 | (cp932[256 * (key[n] ^ 0x80) + i] & KCLS_DT1);
#if 0
                  bm |= ((cp932[256 * key[n] + i] & KCLS_K1)
                                 || (cp932[256 * (key[n] ^ 0x80) + i] & KCLS_K1)
                                 ? KCLS_K2 : 0);
#endif
                }
          if (c & (KCLS_AN | KCLS_KA | KCLS_K2))
                for (j = 0; j < 256; j++)
                {
                  bm |= cp932[256 * i + j] & (KCLS_AN | KCLS_KA | KCLS_K1
                                                                          | KCLS_DT0);
#if 0
                  if (j >= 127 && !(n == 0 || n == 1))
                        break;
#endif
                }
          kcls[n + 1].map[i] = bm;
#endif
          if (i >= 128 && !(n == 0 || n == 1))
                kcls[n + 1].map[i - 128] |= kcls[n + 1].map[i];
        }

  if (n < 6)
        kcls[n + 1].map[0x00] = kcls[n + 1].map[0x80] = 0;
  if (n == 6)
        kcls[7].map[0x00] |= KCLS_AN;
}

unsigned
dt_get(int kdn,
           int xn,
           int n,
           int ch)
{
  int i;
#if DEBUG>=1
  printf("*dt_get(%d)%c%c%c%c(%02X%02X:%02X%02X)->ch=%d",
                 n,
                 kd[kdn]->c[0], kd[kdn]->c[1], kd[kdn]->c[2], kd[kdn]->c[3],
                 kd[kdn]->c[0], kd[kdn]->c[1], kd[kdn]->c[2], kd[kdn]->c[3],
                 ch);
#endif
  /* まずは数える */
  for (i = 0;
           kd[kdn][i].c[xn] == kd[kdn]->c[xn];
           i++)
        ;
  assert(i > 0);
  kd[kdn] += ch % i;
#if DEBUG>=1
  printf("/%d\n dt_get:  %c%c%c%c(%02X%02X:%02X%02X)->ch=%d\n",
                 i,
                 kd[kdn]->c[0], kd[kdn]->c[1], kd[kdn]->c[2], kd[kdn]->c[3],
                 kd[kdn]->c[0], kd[kdn]->c[1], kd[kdn]->c[2], kd[kdn]->c[3],
                 ch);
#endif
  return kd[kdn]->c[n];
}

/* マップから文字を拾ってセット */
unsigned
key_set(int n, unsigned ch)
{
  int cnt = 0, i;

  if (3 <= n && n < 7 && kd[n - 3])
        {
          return dt_get(n - 3, 2, 3, ch);
          return kd[n - 3]->c[3];
        }
  else if (2 <= n && n < 6 && kd[n - 2])
        {
          return dt_get(n - 2, 1, 2, ch);
          return kd[n - 2]->c[2];
        }
  else if (1 <= n && n < 5 && kd[n - 1])
        {
          return dt_get(n - 1, 0, 1, ch);
          return kd[n - 1]->c[1];
        }

#if DEBUG>=3
  if (cnt == 0)
        {
          printf("n=%d, ch=%d, (n-1)=%02X\n", n, ch, key[n - 1]);
          int j;
          for (i = 0; i < 16; i++)
                {
                  printf("map[0x%02X] =", 16 * i);
                  for (j = 0; j < 16; j++)
                        printf(" %03X", kcls[n].map[16 * i + j]);
                  printf("\n");
                }
        }
#endif
  for (i = 0; i < 256; i++)
        {
          if (kcls[n].map[i])
                {
                  if (ch-- == 0)
                        return i;
                  cnt++;
                }
          if (n != 1 && n != 2 && i >= 127)
                break;
        }
  /* 見つからなかったのでもいっぺん */
  assert(cnt > 0);
  ch %= cnt;
  for (i = 0; i < 256; i++)
        if (kcls[n].map[i])
          {
                if (ch-- == 0)
                  return i;
          }
  assert(!"not matched");
  return 0;
}

/* bitwise key をセット */
static
void
key_set64(struct KEY *key64,
                  int n,
                  unsigned k,
                  unsigned vk,
                  unsigned sk)
{
  int i;
  if (!((vk | sk) & 0x7F))
        return;

  for (i = 0; i < 7; i++)
        {
          if (n == 7 && i < 6) continue;
          if (sk & (1 << i))
                {
                  /* セット */
                  int o = tr_pc1[n][6 - i] - 1;
                  if (o < 28)
                        {
                          assert(o >= 0);
                          key64->k[0][0][o].a[0]
                                = key64->k[0][0][o].a[1]
                                = key64->k[0][1][o].a[0]
                                = key64->k[0][1][o].a[1]
                                = -!!(k & (1 << i));
                        }
                  else
                        {
                          assert(o >= 28);
                          assert(o < 56);
                          key64->k[1][0][o - 28].a[0]
                                = key64->k[1][0][o - 28].a[1]
                                = key64->k[1][1][o - 28].a[0]
                                = key64->k[1][1][o - 28].a[1]
                                = -!!(k & (1 << i));
                        }
                }
          else if (vk & (1 << i))
                {
                  /* 反転 */
                  int o = tr_pc1[n][6 - i] - 1;
                  if (o < 28)
                        {
                          assert(o >= 0);
                          key64->k[0][0][o].a[0]
                                = key64->k[0][0][o].a[1]
                                = key64->k[0][1][o].a[0]
                                = key64->k[0][1][o].a[1]
                                = ~key64->k[0][0][o].a[0];
                        }
                  else
                        {
                          assert(o >= 28);
                          assert(o < 56);
                          key64->k[1][0][o - 28].a[0]
                                = key64->k[1][0][o - 28].a[1]
                                = key64->k[1][1][o - 28].a[0]
                                = key64->k[1][1][o - 28].a[1]
                                = ~key64->k[1][0][o - 28].a[0];
                        }
                }
        }
}

/* 指定されたクラスの開始値にリセット
   直前の文字のクラスに縛られる */
int
key_reset(int n)
{
  int i, j;
  unsigned c;

  if (n >= 8)
        return 1;
  if (n == 7)
        {
          key[7] = 0;
          return 1;
        }

  /* 0-2 文字目はランダムに決める
         3 文字目以降は初期値に */
  if (n >= 3)
        key[n] = key_set(n, 0);
  else
        key[n] = key_set(n, rand());

#if DEBUG>=3
  printf("key[%d]=%02X ncls=%04X\n", n, key[n], kcls[n].map[key[n]]);
#endif

  /* セットされた文字を元に、次キャラの文字クラスを決める */
#if 1
  key_make_map(n);
#else
  for (i = 0; i < 256; i++)
        {
          unsigned bs = 0, bm = 0;
          unsigned c = kcls[n].map[key[n]];
#if 1
          if (c & KCLS_K1)
                bm |= ((cp932[256 * key[n] + i] & KCLS_K1)
                           || (cp932[256 * (key[n] ^ 0x80) + i] & KCLS_K1)
                           ? KCLS_K2 : 0);
          else if (c & (KCLS_AN | KCLS_KA | KCLS_K2))
                for (j = 0; j < 256; j++)
                {
                  bm |= cp932[256 * i + j] & (KCLS_AN | KCLS_KA | KCLS_K1);
#if 0
                  if (j >= 127 && !(n == 0 || n == 1))
                        break;
#endif
                }
          kcls[n + 1].map[i] = bm;
#endif
          if (i >= 128 && !(n == 0 || n == 1))
                kcls[n + 1].map[i - 128] |= kcls[n + 1].map[i];
        }

  if (n == 6)
        kcls[7].map[0] |= KCLS_AN;
#endif

  return key_reset(n + 1);
}

/* 指定された鍵空間の中で、キーをひとつ進める
   安全にインクリメントできた場合 true を返す */
static
int
key_inc(int n)
{
  if (n >= 8)
        return 0;
  else if (n == 7)
        {
          key[7] = (key[7] + 64) & 127;
          if (key[7]) return 1;
          else return 0;
        }
  else if (key_inc(n + 1)
                   /*
                        && key_inc(n + 1)
                   && key_inc(n + 1)
                   && key_inc(n + 1)*/
                   )
        return 1;

  /* Salt はインクリメントしない約束にする */
  if (n == 1 || n == 2)
        return 1;

#if DEBUG>=3
  printf("key_inc(n=%d,ck=%02X)\n", n, key[n]);
#endif

  /* 辞書語はインクリメントしていい約束にする */
  if (3 <= n && n < 7 && kd[n - 3])
        {
          if ((key[n - 3] & 0x7F) == ((kd[n - 3] + 1)->c[0] & 0x7F)
                  && (key[n - 2] & 0x7F) == ((kd[n - 3] + 1)->c[1] & 0x7F)
                  && (key[n - 1] & 0x7F) == ((kd[n - 3] + 1)->c[2] & 0x7F))
                {
                  memcpy(&key[n - 3], &(++kd[n - 3])->c[0], 4);
#if DEBUG>=2
                  printf(">dt_get:%c%c%c%c(%02X%02X:%02X%02X)\n",
                                 kd[n - 3]->c[0], kd[n - 3]->c[1], kd[n - 3]->c[2], kd[n - 3]->c[3],
                                 kd[n - 3]->c[0], kd[n - 3]->c[1], kd[n - 3]->c[2], kd[n - 3]->c[3]);
#endif
                  return 1;
                }
          else
                {
                  return 0;
                }
        }
  else if (2 <= n && n < 6 && kd[n - 2])
        {
          if ((key[n - 2] & 0x7F) == ((kd[n - 2] + 1)->c[0] & 0x7F)
                  && (key[n - 1] & 0x7F) == ((kd[n - 2] + 1)->c[1] & 0x7F))
                {
                  memcpy(&key[n - 2], &(++kd[n - 2])->c[0], 4);
#if DEBUG>=2
                  printf(">dt_get:%c%c%c%c(%02X%02X:%02X%02X)\n",
                                 kd[n - 2]->c[0], kd[n - 2]->c[1], kd[n - 2]->c[2], kd[n - 2]->c[3],
                                 kd[n - 2]->c[0], kd[n - 2]->c[1], kd[n - 2]->c[2], kd[n - 2]->c[3]);
#endif
                  return 1;
                }
          else
                {
                  return 0;
                }
          if (kd[n - 2]->c[0] == key[n - 2])
                return 1;
          else
                return 0;
        }
  else if (1 <= n && n < 5 && kd[n - 1])
        {
          unsigned c2 = kd[n - 1]->c[0];
          if ((0x81 <= c2 && c2 <= 0x9F)
                  || (0xE0 <= c2 && c2 <= 0xFC))
                {
                  kd[n - 1] = NULL;
#if 0
                  if (!(n == 1 && n == 2))
                        key[n] &= 0x7F;
                  if (!(n == 2 && n == 3))
                        key[n - 1] &= 0x7F;
#endif
                  key_make_map(n - 1);
                }
          else if ((key[n - 1] & 0x7F) == ((kd[n - 1] + 1)->c[0] & 0x7F))
                {
                  memcpy(&key[n - 1], &(++kd[n - 1])->c[0], 4);
#if DEBUG>=2
                  printf(">dt_get:%c%c%c%c(%02X%02X:%02X%02X)\n",
                                 kd[n - 1]->c[0], kd[n - 1]->c[1], kd[n - 1]->c[2], kd[n - 1]->c[3],
                                 kd[n - 1]->c[0], kd[n - 1]->c[1], kd[n - 1]->c[2], kd[n - 1]->c[3]);
#endif
                  return 1;
                }
          else
                {
                  return 0;
                }
#if 0
          if (kd[n - 1]->c[0] == key[n - 1])
                return 1;
          else
                return 0;
#endif
        }
  else if (n < 4 && kd[n])
        {
          if (0 && kd[n]->c[0] == key[n])
                return 1;
          kd[n] = NULL;
#if 0
          if (!(n == 1 || n == 2))
                key[n] &= 0x7F;
#endif
        }

  /* 実際に増やしてみる */
  assert(n >= 3);
  for (;;)
        {
          if (n <= 3
                  && !(key[n] & 0x80)
                  && kcls[n].map[key[n] ^ 0x80] & (KCLS_DT0))
                {
                  /* 半角カタカナの1バイト目 */
                  key[n] ^= 0x80;
                }
          else
                {
                  key[n] = (key[n] & 0x7F) + 1;
                  if (key[n] >= 0x80)
                        return 0;
                }

          if (kcls[n].map[key[n]])
                {
                  key_make_map(n);
                  key_reset(n + 1);
                  return 1;
                }
        }
  while (++key[n] < 0x80)
        {
          if (kcls[n].map[key[n]])
                {
                  key_make_map(n);
                  key_reset(n + 1);
                  return 1;
                }
        }
  return 0;
}

/* 鍵を完全にリセットする
   Saltもセットし直す */
static
void
key_init()
{
  int i, j;

#if USE_DT
  /* 辞書を、インデクスを作りながらマップにはめこんで逝く
         辞書はコード順昇順に並んでるものとする */
  for (i = 0; i < dtcnt; i++)
        {
          unsigned c = dt[i].c[0];

          assert(dt[i].c[0]
                         && dt[i].c[1]
                         && dt[i].c[2]
                         && dt[i].c[3]);

          /* BSD 鯖でしにそうな文字は残念ながら除外 */
          assert((dt[i].c[0] & 0x7F)
                         && (dt[i].c[1] & 0x7F)
                         && (dt[i].c[2] & 0x7F)
                         && (dt[i].c[3] & 0x7F));

          /* インデクス */
          if (!dtidx[c])
                dtidx[c] = &dt[i];

          if ((0x81 <= c && c <= 0x9F)
                  || (0xE0 <= c && c <= 0xFC))
                {
                  /* 全角なので、2バイトきまった時点で立てる */
                  cp932[256 * c + dt[i].c[1]] |= KCLS_DT1;
                }
          else if (0xA1 <= c && c <= 0xDF)
                {
                  /* 半角カナ */
                  for (j = 0; j < 256; j++)
                        cp932[256 * c + j] |= KCLS_DT0;
                }
        }
  /* ケツ、ちうか番人 */
  dtidx[0x100] = &dt[i];
#endif

  key[8] = 0;

  /* 初期マップを組む */
  for (i = 0; i < 256; i++)
        {
          unsigned bm = 0;
          kcls[0].map[i] = 0;
          for (j = 0; j < 256; j++)
                bm |= cp932[256 * i + j];
          kcls[0].map[i] = bm & (KCLS_AN | KCLS_KA | KCLS_K1
                                                         | KCLS_DT0
                                                         );
          if (i >= 128)
                kcls[0].map[i - 128] |= kcls[0].map[i];
        }

  key_reset(0);
}

/***************************************************************
 *
 *      可視文字列に変換
 *      n = 0, flag !=0 で呼ぶこと
 *
 *      ptr で指される文字列は、変換に成功したら書き換えられる
 *
 *      成功したら flg, 失敗したら 0 を返す。
 *
 */

unsigned
translate(unsigned char *ptr,
                  int n,
                  unsigned flag)
{
  int r;
  unsigned char buf[32];
  unsigned s0 = (n == 1 || n == 2 ? 0x00 : 0x80);
  unsigned s1 = (n == 0 || n == 1 ? 0x00 : 0x80);
  unsigned c0 = ptr[n] << 8;
  unsigned c1 = ptr[n + 1];
  unsigned cs0 = c0 ^ (s0 << 8);
  unsigned cs1 = c1 ^ s1;

  if (n >= 8)
        return flag;

  if (n == 7)
        {
          int i;
          /* 最後の1文字 */
          if (!(ptr[7] & 0x7F))
                return flag;
          
          for (i = 0x00; i <= 0x7E; i++)
                {
                  if (cp932[c0 | i] & KCLS_K1)
                        {
                          ptr[8] = i;
                          return flag;
                        }
                  if (cp932[c0 | (0x80 + i)] & KCLS_K1)
                        {
                          ptr[8] = 0x80 + i;
                          return flag;
                        }
                }

          ptr[7] ^= 0x80; c0 = ptr[7] << 8;
          for (i = 0x00; i <= 0x7E; i++)
                {
                  if (cp932[c0 | i] & KCLS_K1)
                        {
                          ptr[8] = i;
                          return flag;
                        }
                  if (cp932[c0 | (0x80 + i)] & KCLS_K1)
                        {
                          ptr[8] = 0x80 + i;
                          return flag;
                        }
                }
          ptr[7] ^= 0x80; c0 = ptr[7] << 8;
        }

  /* K1 */
  if (cp932[c0 | c1] & KCLS_K1)
        {
          r = translate(ptr, n + 2, flag);
          if (r)
                return r;
        }
  if (s0
          && cp932[cs0 | c1] & KCLS_K1)
        {
          memcpy(buf, ptr, sizeof(buf));
          buf[n] ^= s0;
          r = translate(buf, n + 2, flag);
          if (r)
                {
                  memcpy(ptr, buf, sizeof(buf));
                  return r;
                }
        }
  if (s1
          && cp932[c0 | cs1] & KCLS_K1)
        {
          memcpy(buf, ptr, sizeof(buf));
          buf[n + 1] ^= s1;
          r = translate(buf, n + 2, flag);
          if (r)
                {
                  memcpy(ptr, buf, sizeof(buf));
                  return r;
                }
        }
  if (s0 && s1
          && cp932[cs0 | cs1] & KCLS_K1)
        {
          memcpy(buf, ptr, sizeof(buf));
          buf[n] ^= s0;
          buf[n + 1] ^= s1;
          r = translate(buf, n + 2, flag);
          if (r)
                {
                  memcpy(ptr, buf, sizeof(buf));
                  return r;
                }
        }

  /* AN */
  if (cp932[c0] & (KCLS_AN | KCLS_KA))
        {
          r = translate(ptr, n + 1, flag);
          if (r)
                return r;
        }
  if (s0 && cp932[cs0] & (KCLS_AN | KCLS_KA))
        {
          memcpy(buf, ptr, sizeof(buf));
          buf[n] ^= s0;
          r = translate(buf, n + 1, flag);
          if (r)
                {
                  memcpy(ptr, buf, sizeof(buf));
                  return r;
                }
        }

  /* KA */
  /* KG */
  /* KD */
  /* AD */

  return 0;
}

/***************************************************************
 *
 *      Salt のセット
 *      オペランドのオフセットを書き換えて回ってるので注意
 *
 */

void
set_salt(signed char *code,
                 unsigned char const *k)
{
  int i, j;

  for (i = 0; i < 2; i++)
        {
          unsigned s = k[1 + i] & 255;
          if (s > 'z')
                s = 0;
          else if (s >= 'a')
                s = s - 'a' + 2 + 10 + 26;
          else if (s >= 'A')
                s = s - 'A' + 2 + 10;
          else if (s >= '.')
                s = s - '.';
          else
                s = 0;

#if DEBUG>=1
          printf("Salt %d:%3o\n", i, s & 63);
#endif
          for (j = 0; j < 6; j++)
                {
#if DEBUG>=2
                  printf("Salt %d:%d %+3d:%+3d",
                                 i, j,
                                 code[loo - crypt64_sta + los[6 * i + j     ]],
                                 code[loo - crypt64_sta + los[6 * i + j + 24]]);
#endif
                if (s & (1 << j))
                  {
                        code[loo - crypt64_sta + los[6 * i + j     ]] = 8 * ((4 * i + j + 15) & 31) - 128;
                        code[loo - crypt64_sta + los[6 * i + j + 24]] = 8 * ((4 * i + j -  1) & 31) - 128;
                  }
                else
                  {
                        code[loo - crypt64_sta + los[6 * i + j     ]] = 8 * ((4 * i + j -  1) & 31) - 128;
                        code[loo - crypt64_sta + los[6 * i + j + 24]] = 8 * ((4 * i + j + 15) & 31) - 128;
                  }
                code[loo - crypt64_sta + los[6 * i + j + 12]] = 8 * ((4 * i + j +  7) & 31) - 128;
                code[loo - crypt64_sta + los[6 * i + j + 36]] = 8 * ((4 * i + j + 23) & 31) - 128;
#if DEBUG>=2
                  printf(" => %+3d:%+3d\n",
                                 code[loo - crypt64_sta + los[6 * i + j     ]],
                                 code[loo - crypt64_sta + los[6 * i + j + 24]]);
#endif
                }
        }
}

/***************************************************************
 *
 *      オペコードを展開
 *
 *      op
 *              0x6F    MOVQ
 *              0x7F    STORE
 *              0xDB    PAND
 *              0xDF    PANDN
 *              0xEB    POR
 *              0xEF    PXOR
 *
 *      r       EAX, ECX, EDX, EBX
 *              ESP, EBP, ESI, EDI
 *
 */

static
signed char *
reg_op(signed char *pc,
           unsigned op,
           unsigned d,
           unsigned s)
{
  pc[0] = 0x0F;
  pc[1] = op;
  /* 11 ddd sss */
  pc[2] = (0300
                   | ((d << 3) & 0070)
                   | (s & 0007));
  return pc + 3;
}

static
signed char *
reg_mem(signed char *pc,
                unsigned op,
                unsigned d,
                unsigned s,
                long ofs)
{
  pc[0] = 0x0F;
  pc[1] = op;
  if (-128 <= ofs && ofs <= 127)
        {
          /* short ofs
                 01 ddd sss [ofs.b] */
          pc[2] = (0100
                           | ((d << 3) & 0070)
                           | (s & 0007));
          pc[3] = ofs;
          return pc + 4;
        }
  else
        {
          /* long ofs
                 10 ddd sss [ofs.l] */
          pc[2] = (0200
                           | ((d << 3) & 0070)
                           | (s & 0007));
          *(long *)&pc[3] = ofs;
          return pc + 7;
        }
}

/***************************************************************
 *
 *      与えられた式を解析・命令生成
 *
 *      ^               先頭固定
 *      $               末尾固定
 *      ?               任意の1文字
 *      *               任意の0文字以上
 *      &               大小区別ナシ、グループに使われた場合、capitalize
 *      ()              グループ化
 *      \s              or
 *      \1              一致したグループ(実体)
 *      $(fn)   テキストを展開(グループはクラスとして扱われる)
 *
 *                      以下、クラス展開のメタキャラ
 *      [A-Z]   文字クラス定義 ^ は排他
 *      {}              0文字以上
 *      {n}             n文字
 *      {n,}    n文字以上
 *      {,n}    n文字以下
 *      {m,n}   m-n文字
 *
 */

static
int
cv64(int c)
{
  if ('.' <= c && c <= '/')
        return c - '.';
  else if ('0' <= c && c <= '9')
        return c - '0' + 2;
  else if ('A' <= c && c <= 'Z')
        return c - 'A' + 2 + 10;
  else if ('a' <= c && c <= 'z')
        return c - 'a' + 2 + 10 + 26;
  else
        return -1;
}

static
int
expr_make(signed char *iptr,
                  int ofs,
                  char const *expr,
                  int len)
{
  /* 先頭制約 */
  signed char *o_iptr = iptr;
  unsigned op = 0x6F;
  int i;

  if (expr[0] == '^')
        {
          if (len == 0 || ofs > 0)
                return -1;
          expr++;
          len--;
        }

  /* 一文字づつ展開 */
  for (i = 0; i < len; i++)
        {
          int c = expr[i];

          if (c == '$')
                {
                  assert(op != 0x6F);
                  if (ofs < 10)
                        return 0;
                  else if (ofs > 10)
                        return -1;
                  return iptr - o_iptr;
                }

          if (ofs >= 10)
                return -1;

          if (c == '[')
                {
                  /* クラスをまとめる */
                  unsigned oop; /* MOVQ */
                  int j;
                  int cs[64];
                  memset(cs, 0, 64 * sizeof(int));
                  for (i++; c = expr[i], c != ']'; i++)
                        {
                          c = cv64(c);
                          if (c < 0)
                                return -1;
                          if (expr[i + 1] == '-')
                                {
                                  int ce = cv64(expr[i + 2]);
                                  if (ce < 0)
                                        return -1;
                                  while (c <= ce)
                                        cs[c++]++;
                                  i += 2;
                                }
                          else
                                cs[c]++;
                        }
                  assert(c == ']');

                  /* マップされたモノから命令を生成する */
                  oop = 0x6F;   /* MOVQ */
                  for (j = 0; j < 64; j++)
                        if (cs[j])
                          {
                                if (ofs == 9 && (j & 3))
                                  continue;
                                iptr = reg_mem(iptr,
                                                           oop,
                                                           1,           /* MM1 */
                                                           5,           /* EBP */
                                                           8 * (64 * ofs + j) + 8 * 32 - 8 * 16);
                                oop = 0xEB;
                          }
                  if (oop != 0xEB)
                        {
                          if (ofs == 9)
                                return -1;
                        }
                  else
                        {
                          iptr = reg_op(iptr,
                                                        op,
                                                        0,              /* MM0 */
                                                        1);             /* MM1 */
                          op = 0xDB;
                        }
                  ofs++;
                }
          else if (c == '?')
                {
                  ofs++;
                }
          else if ((c = cv64(c)) >= 0)
                {
                  if (ofs == 9 && (c & 3))
                        return -1;
                  iptr = reg_mem(iptr,
                                                 op,
                                                 0,             /* MM0 */
                                                 5,             /* EBP */
                                                 8 * (64 * ofs + c) + 8 * 32 - 8 * 16);
                  op = 0xDB;
                  ofs++;
                }
          else
                return -1;
        }

  return iptr - o_iptr;
}
/*
Fighters ^FIGHTERS ^BayStars ^Red[Ss]tar/ ^REDSTAR/ ^Parsifal ^VALKYRIE ^Valkyrie 
^Dr.Death ^IamCHONO ^RAGNAROK ^MARAOH.. ^MARAOH// ......... God[Ff]ather GODFATHER 
^maraGULO[./] BLACKJACK ^[Bb]lackjack ^BlackJack [Pp]atagonia PATAGONIA ^JC.PENNEY 
^JC.Penney ^syombolic ROCKNROLL stammerB4U Ms.Erie.W. MARA.w/w/w R3[0-4]SKYLINE 
100000[Gg]et. 100000GET. 
*/
signed char *
expr_parse(signed char *iptr,
                   int codesiz_limit,
                   char const *expr)
{
  char expr_buf[65536 + 1];
  FILE *fp;
  size_t sz;

  /* ファイルを読み込む
         この版では手抜きで 64K 制限 */
#define TARGET_SIZ 65536
  fp = fopen("target.txt", "rb");
  memset(expr_buf, 0, TARGET_SIZ + 1);
  sz = fread(expr_buf, sizeof(char), TARGET_SIZ, fp);
  fclose(fp);

  /* XXX ターゲットのサイズをチェック */
  if (sz == TARGET_SIZ)
        {
          /* トークンのトラバース */
          char *ds, *pe, *ps;
          for (ds = &expr_buf[TARGET_SIZ - 1];
                   !isspace(*ds);
                   ds--)
                assert(ds >= expr_buf);
          for (pe = ds++; isspace(*pe); pe--)
                assert(pe >= expr_buf);
          for (ps = pe++; !isspace(*ps); ps--)
                assert(ps >= expr_buf);
          fprintf(stderr, "WARNING: <");
          ps++;
          while (ps < pe)
                fputc(*ps++, stderr);
          fprintf(stderr, ">より後ろのターゲット<%s(ry>はオ�ル\n",
                          ds);
          *pe = 0;
        }

  /* PXOR MM7,MM7 */
  iptr = reg_op(iptr, 0xEF, 7, 7);

  /* 順繰りに parse */
  expr = expr_buf;
  while (expr[0])
        {
          char const *p;
          int i;

          /* 頭の Whitespace を読み飛ばす */
          while (isspace(expr[0]))
                expr++;

          if (!expr[0])
                break;

          /* トークンを切り出す */
          for (p = expr; expr[0] && !isspace(expr[0]); expr++)
                ;

          /* 展開する */
          for (i = 0; i < 10; i++)
                {
                  int n = expr_make(iptr, i, p, expr - p);
                  if (n < 0)
                        break;
#if DEBUG>=1
                  if (n > 0)
                        {
                          int j;
                          for (j = 0; &p[j] < expr; j++)
                                putchar(p[j]);
                          printf(": of=%d len=%d\n", i, expr - p);
                        }
#endif
                  if (n > 0)
                        iptr = reg_op(iptr + n,
                                                  0xEB,
                                                  7,
                                                  0);
                }
        }

  return reg_mem(iptr,
                                 0x7F,
                                 7,
                                 5,
                                 8 * 31 - 8 * 16);
}

static
unsigned long
usec()
{
#ifdef __GNUC__
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return 100 * tv.tv_sec + (tv.tv_usec / 10000);
#else
  struct timeb tm;
  ftime(&tm);
  return 100 * tm.time + tm.millitm / 10;
#endif
}

/***************************************************************
 *
 *      メインループとか
 *
 */

/* 定数項 */
static struct SLICE const sk6[] =
{
  {0xAAAAAAAAUL, 0xAAAAAAAAUL},
  {0xCCCCCCCCUL, 0xCCCCCCCCUL},
  {0xF0F0F0F0UL, 0xF0F0F0F0UL},
  {0xFF00FF00UL, 0xFF00FF00UL},
  {0xFFFF0000UL, 0xFFFF0000UL},
  {0x00000000UL, 0xFFFFFFFFUL},
};

#ifndef __GNUC__
//typedef int (__msfastcall *CRYPT64_PP)(unsigned long const *k, unsigned long *lr);
typedef int (*CRYPT64_PP)(unsigned long const *k, unsigned long *lr);
#endif

int dmy;

struct KEY key64;
struct PARAM param64;

int
main(int argc, char *argv[])
{
  int i, j;
  int lc;
  int mincnt;
  signed char *code = NULL;
  FILE *ofp;
  int n_iter;
  int cr;

#define N_TS 4
  struct
  {
        unsigned t;
        int c;
  } ts[N_TS];

#ifndef __GNUC__
  CRYPT64_PP d_crypt64;
#endif

#if 0
  if (argc < 2)
        {
          fprintf(stderr, "式きぼんぬ\n");
          return 1;
        }
#endif

  /* t[16] は、内部演算で使用する、all 1 が入っている */
  param64.t[16].a[0] = param64.t[16].a[1] = 0xFFFFFFFFUL;

  /* 固定キーのコピー */
  for (i = 0; i < 6; i++)
        {
          int o = tr_pc1[7][6 - i] - 1;
          if (o < 28)
                {
                  key64.k[0][0][o] = key64.k[0][1][o] = sk6[i];
                }
          else
                {
                  o -= 28;
                  key64.k[1][0][o] = key64.k[1][1][o] = sk6[i];
                }
        }

  /* Saltを加味しない場合は、コード領域を
         writable 領域に展開しなくてもよい。
         [XXX] OSによっては、書込&実行可能領域を専用のサーヴィスで
         取得しなければならないものもあるかもしれないので、注意 */
#ifdef __WIN32
  HANDLE h = CreateFileMapping(INVALID_HANDLE_VALUE,
                                                           NULL,
                                                           PAGE_EXECUTE_READWRITE,
                                                           0, 0x20000000,
                                                           NULL);
  if (SUCCEEDED(h))
        code = (signed char *)MapViewOfFile(h,
                                                                                SECTION_MAP_EXECUTE | FILE_MAP_WRITE,
                                                                                0, 0x10000000,
                                                                                0);

#else
  code = (signed char *)mmap(NULL,
                             0x10000000,
                             PROT_EXEC | PROT_READ | PROT_WRITE,
                             MAP_PRIVATE | MAP_ANONYMOUS,
                             1, /* fd */
                             0);
  if ((void *)code == MAP_FAILED)
        code =NULL;
#endif

  /* メモリが確保できていない場合のいんちき対策 */
  if (code == NULL)
        code = (signed char *)malloc(crypt64_end - crypt64_sta + 1024 * 1024);
  assert(code != NULL);

  /* Prologue を展開 */
  memcpy(code, crypt64_sta, crypt64_end - crypt64_sta);
#ifndef __GNUC__
  d_crypt64 = (CRYPT64_PP)code;
#endif
  memcpy(expr_parse(code + (crypt64_end - crypt64_sta),
                                        1024 * 1024 - (crypt64_ep_end - crypt64_ep),
                                        argv[1]),
                 crypt64_ep,
                 crypt64_ep_end - crypt64_ep);

  /* キーの初期化 */
  srand(time(NULL));
  key_init();
  set_salt(code, key);
  for (i = 0; i < 8; i++)
        key_set64(&key64, i, okey[i] = key[i], 0, 0x7F);

#if DEBUG>=1
  printf("key=%p param=%p\n", &key64, &param64);
#endif
  assert(!((unsigned)&key64 & 7));
  assert(!((unsigned)&param64 & 7));

  if ((ofp = fopen("log.txt", "at")) != NULL)
        setvbuf(ofp, NULL, _IOLBF, BUFSIZ);

  for (i = 0; i < N_TS; i++)
        ts[i].t = ts[i].c = 0;

  mincnt = 0x7FFFFFFF;
  n_iter = 0;
  cr = 0;
  /* 探索ループだぞっと */
  for (;;)
        {
          int cnt;
          int k, kk;

          /* 鍵のセット */
#if 1
          for (i = 0; i < 8; i++)
                {
                  key_set64(&key64, i, key[i], key[i] ^ okey[i], 0);
                  okey[i] = key[i];
                }
#if 0
                for (j = 0; j < 7; j++)
                  {
                        int o = tr_pc1[i][6 - j] - 1;
                        if (i == 7 && j < 6) continue;
                        if (o < 28)
                          {
                                assert(o >= 0);
                                key64.k[0][0][o].a[0]
                                  = key64.k[0][0][o].a[1]
                                  = key64.k[0][1][o].a[0]
                                  = key64.k[0][1][o].a[1]
                                  = -!!(key[i] & (1 << j));
                          }
                        else
                          {
                                assert(o >= 28);
                                assert(o < 56);
                                key64.k[1][0][o - 28].a[0]
                                  = key64.k[1][0][o - 28].a[1]
                                  = key64.k[1][1][o - 28].a[0]
                                  = key64.k[1][1][o - 28].a[1]
                                  = -!!(key[i] & (1 << j));
                          }
                  }
#endif
#endif

          /* まずは LR を初期化 */
                //memset(param64.lr, 0, sizeof(param64.lr));
          /* 呼ぶ! */
#ifdef __GNUC__
          asm volatile("call *%3"
                                   : "=a"(cnt)
                                   : "c"(key64.k), "d"(param64.lr), "m"(code)
                                   //: "c"(key64.k), "d"(param64.lr), "m"(crypt64_sta)
                                   : "memory");
#else
          cnt = (*d_crypt64)(key64.k[0][0][0].a, param64.lr[0][0].a);
#endif
          if (mincnt > cnt && cnt > 0)
                {
                  mincnt = cnt;
                  if (cr)
                        fprintf(stderr, "\n");
                  cr = 0;
                  fprintf(stderr, "cycle=%d\n", cnt);
                }
          /* XXX 手抜きのため、ワークにはみ出ている2ビットを落とす */
          memset(param64.t[0].a, 0, 2 * 8);

          /* ヒットしたときの処理 */
          for (kk = 0; kk < 2; kk++)
                {
                  unsigned t;
//continue;/*XXX*/
                  t = param64.t[31].a[kk];
#if 1
                  if (!t)
                        continue;
#endif
                  for (k = 0; k < 32; k++)
                        {
                          char hash[16];
                          unsigned char buf[32];
#if 1
                          if (!(t & (1 << k)))
                                continue;
#endif
                          for (i = 1; i < 11; i++)
                                {
                                  unsigned c = 0;
                                  for (j = 0; j < 6; j++)
                                        c = (c << 1) | !!(param64.lr[0][tr_fp[6 * i + j]].a[kk] & (1 << k));
                                  hash[i - 1] = c["./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"];
                                }
                          hash[10] = 0;

                          memcpy(buf, key, 32);
                          buf[8] = buf[9] = 0;
                          buf[7] = (buf[7] & 0x40) + 32 * kk + k;
                          if (translate(buf, 0, 1))
                                {
                                  if (cr)
                                        fprintf(stderr, "\n");
                                  cr = 0;
                                  printf("◆%s #%-10.10s(%02X %02X %02X %02X %02X %02X %02X %02X/%02X)\n",
                                                 hash,
                                                 buf,
                                                 buf[0], buf[1], buf[2], buf[3],
                                                 buf[4], buf[5], buf[6], buf[7],
                                                 buf[8]);
                                  if (ofp)
                                        fprintf(ofp,
                                                        "◆%s #%-10.10s(%02X %02X %02X %02X %02X %02X %02X %02X/%02X)\n",
                                                        hash,
                                                        buf,
                                                        buf[0], buf[1], buf[2], buf[3],
                                                        buf[4], buf[5], buf[6], buf[7],
                                                        buf[8]);
                                }
                          else
                                {
#if DEBUG>=1
                                  if (cr)
                                        fprintf(stderr, "\n");
                                  cr = 0;
                                  printf("◆%s            (%02X %02X %02X %02X %02X %02X %02X %02X   )\n",
                                                 hash,
                                                 buf[0], buf[1], buf[2], buf[3],
                                                 buf[4], buf[5], buf[6], buf[7]);
                                  if (ofp)
                                        fprintf(ofp,
                                                        "◆%s            (%02X %02X %02X %02X %02X %02X %02X %02X   )\n",
                                                        hash,
                                                        buf[0], buf[1], buf[2], buf[3],
                                                        buf[4], buf[5], buf[6], buf[7]);
#endif
                                }
                        }
                }

          if (++n_iter - ts[0].c >= 8192)
                {
                  int t = usec();
                  if (ts[N_TS - 1].c)
                        {
                          int a = 100 * 64 * (n_iter - ts[N_TS - 1].c) / (t - ts[N_TS - 1].t);
                          fprintf(stderr,
                                          "%8d.%03d(ktrips/sec)\r",
                                          a / 1000,
                                          a % 1000);
                          cr++;
                        }
                  for (i = N_TS - 1; i >= 1; i--)
                        ts[i] = ts[i - 1];
                  ts[0].c = n_iter;
                  ts[0].t = t;
                  for (i = 1; i < N_TS; i++)
                        if (ts[i].c)
                          break;
                        else
                          ts[i] = ts[i - 1];
                }
#if 1
          if (!key_inc(3))
                {
#if DEBUG>=2
                  printf("********************************\n");
#endif
                  key_reset(0);
                  set_salt(code, key);
                  for (i = 0; i < 8; i++)
                        key_set64(&key64, i, okey[i] = key[i], 0, 0x7F);
                }
#endif
        }

  return 0;
}

/*
 *      Local Variables:
 *              tab-width:      4
 *      End:
 *
 * EOF */