branches/mty-makai/mty.c

/***********************************************************************
 *
 *      file: mty.cpp
 *
 *      Ü AŇÄŽB
 *
 *      $Id$
 *
 */

#define DEBUG 0
#define USE_DT 1

#ifndef DEBUG
#define NDEBUG
#endif

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#ifdef __GNUC__

#include <stdint.h>
#define ALIGN_PREFIX(n)
#define ALIGN_SUFFIX(n) __attribute__ ((aligned(n)))
#ifdef __SSE__
typedef unsigned DQWORD_T __attribute__ ((mode(V4SI)));
#endif

#else

#include <xmmintrin.h>
#define ALIGN_PREFIX(n) __declspec(align(16))
#define ALIGN_SUFFIX(n)

/* inttypes.h */
typedef __int32 int32_t;
typedef unsigned __int32 uint32_t;
typedef unsigned __int64 uint64_t;

typedef __m128 DQWORD_T;

#endif

#if defined(WIN32)

#include <windows.h>
#include <sys/timeb.h>

#elif defined(__GNUC__)

#include <sys/mman.h>
#include <sys/time.h>

#endif

#include "crypt64.h"
#include "dt4.h"

#if defined(USE_MMX)

#define N_STRIDE 6
typedef uint64_t        WS_T;
typedef uint32_t        ALU_T;

#elif defined(USE_64_XMM)

#define N_STRIDE 7
typedef DQWORD_T        WS_T;
typedef uint64_t        ALU_T;

#else   /* XMM */

#define N_STRIDE 7
typedef DQWORD_T        WS_T;
typedef uint32_t        ALU_T;

#endif

#define N_I             (sizeof(WS_T) / sizeof(uint32_t))
#define N_ALU (sizeof(WS_T) / sizeof(ALU_T))
#define ALU_BITS (CHAR_BIT * sizeof(ALU_T))

/* Ž]u 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ĹI]u */
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,
};

/* 1rbgŞ */
typedef union SLICE
{
  uint32_t      i[N_I];         /* 32-bit initializer */
  ALU_T         a[N_ALU];       /* C Ĺľ˘âˇ˘TCY */
  WS_T          w;                      /* GR[hĹľ¤TCY */
} SLICE;

/* crypt64() Şň¤p[^ */
struct PARAM
{
  SLICE lr[2][32];
  SLICE t[32];
  SLICE hit[10][64];
  SLICE hiti[10][26];
};

/* ŽÍLR ĆAťĚRs[ŞKv */
struct KEY
{
  SLICE k[2][2][28];
};

/* żNX\ */
unsigned char cp932[0x10000] = {
#include "cp932.inc"
};

/* Žśń */
unsigned char key[8 + 8];
unsigned char okey[8 + 8];

/* ŽNX */
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
/* ŽLpŤCfNX */
struct DT *kd[8 + 8];

/* ŤCfNX */
struct DT *dtidx[0x100 + 1];
#endif

/* wčłę˝NXĆüÁÄ˘éL[ŠçAclassify đs¤ */
void
key_make_map(int n)
{
  int i, j;
  unsigned c = kcls[n].map[key[n]];

  if (3 <= n && n < 7 && kd[n - 3])
        {
          /* ŤĚPcĚśBăëÉijLN^Şé */
          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śđEÁÄ˘ŤÜÂ */
#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)
        {
          /* J^JißÝ˘ŤÜˇ */
          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 đśŹˇéKviV */
  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];
}

/* }bvŠçśđEÁÄZbg */
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 đZbg */
static
void
key_set64(struct KEY *key64,
                  int n,
                  unsigned k,
                  unsigned vk,
                  unsigned sk)
{
  int i, j;
  if (!((vk | sk) & 0x7F))
        return;

  for (i = 0; i < 7; i++)
        {
          if (n == 7 && i < N_STRIDE) continue;
          if (sk & (1 << i))
                {
                  /* Zbg */
                  int o = tr_pc1[n][6 - i] - 1;
                  if (o < 28)
                        {
                          assert(o >= 0);
                          for (j = 0; j < N_ALU; j++)
                                key64->k[0][0][o].a[j]
                                = key64->k[0][1][o].a[j]
                                  = -!!(k & (1 << i));
                        }
                  else
                        {
                          assert(o >= 28);
                          assert(o < 56);
                          for (j = 0; j < N_ALU; j++)
                                key64->k[1][0][o - 28].a[j]
                                  = key64->k[1][1][o - 28].a[j]
                                  = -!!(k & (1 << i));
                        }
                }
          else if (vk & (1 << i))
                {
                  /* ˝] */
                  int o = tr_pc1[n][6 - i] - 1;
                  if (o < 28)
                        {
                          assert(o >= 0);
                          for (j = 0; j < N_ALU; j++)
                          key64->k[0][0][o].a[j]
                                = key64->k[0][1][o].a[j]
                                = ~key64->k[0][0][o].a[j];
                        }
                  else
                        {
                          assert(o >= 28);
                          assert(o < 56);
                          for (j = 0; j < N_ALU; j++)
                                key64->k[1][0][o - 28].a[j]
                                = key64->k[1][1][o - 28].a[j]
                                = ~key64->k[1][0][o - 28].a[j];
                        }
                }
        }
}

/* wčłę˝NXĚJnlÉZbg
   źOĚśĚNXÉçęé */
int
key_reset(int n)
{
  if (n >= 8)
        return 1;
  if (n == 7)
        {
          key[7] = 0;
          return 1;
        }

  /* 0-2 śÚÍ_Éßé
         3 śÚČ~ÍúlÉ */
  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

  /* Zbgłę˝śđłÉALĚśNXđßé */
  key_make_map(n);

  return key_reset(n + 1);
}

/* wčłę˝ŽóÔĚĹAL[đĐĆÂißé
   ŔSÉCNgĹŤ˝ę true đÔˇ */
static
int
key_inc(int n)
{
  if (n >= 8)
        return 0;
  else if (n == 7)
        {
          /* ĹăĚoCg */
          if (N_STRIDE == 7)
                return 0;

          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 ÍCNgľČ˘ńŠÉˇé */
  if (n == 1 || n == 2)
        return 1;

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

  /* ŤęÍCNgľÄ˘˘ńŠÉˇé */
  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))
                {
                  /* źpJ^JiĚ1oCgÚ */
                  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;
}

/* ŽđŽSÉZbgˇé
   SaltŕZbgľźˇ */
static
void
key_init()
{
  int i, j;

#if USE_DT
  /* ŤđACfNXđěčČŞç}bvÉÍßąńĹŔ
         ŤÍR[h¸ÉŔńĹéŕĚĆˇé */
  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 IĹľÉť¤ČśÍcOČŞçO */
          assert((dt[i].c[0] & 0x7F)
                         && (dt[i].c[1] & 0x7F)
                         && (dt[i].c[2] & 0x7F)
                         && (dt[i].c[3] & 0x7F));

          /* CfNX */
          if (!dtidx[c])
                dtidx[c] = &dt[i];

          if ((0x81 <= c && c <= 0x9F)
                  || (0xE0 <= c && c <= 0xFC))
                {
                  /* SpČĚĹA2oCgŤÜÁ˝_Ĺ§Äé */
                  cp932[256 * c + dt[i].c[1]] |= KCLS_DT1;
                }
          else if (0xA1 <= c && c <= 0xDF)
                {
                  /* źpJi */
                  for (j = 0; j < 256; j++)
                        cp932[256 * c + j] |= KCLS_DT0;
                }
        }
  /* PcAż¤ŠÔl */
  dtidx[0x100] = &dt[i];
#endif

  key[8] = 0;

  /* ú}bvđgŢ */
  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 ĹwłęéśńÍAĎˇÉŹ÷ľ˝çŤˇŚçęé
 *
 *      Ź÷ľ˝ç flg, ¸sľ˝ç 0 đÔˇB
 *
 */

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 ĚZbg
 *      IyhĚItZbgđŤˇŚÄńÁÄéĚĹÓ
 *
 */

#if N_STRIDE == 6
#define C(c,i,j,o) (*(int8_t  *)((c) + (loo - crypt64_sta) + los[6 * (i) + (j) + (o)]))
#elif N_STRIDE == 7
#define C(c,i,j,o) (*(int32_t *)((c) + (loo - crypt64_sta) + los[6 * (i) + (j) + (o)]))
#endif

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",
                  printf("Salt %d:%d %08lX:%08lX",
                                 i, j,
                                 C(code, i, j,  0),
                                 C(code, i, j, 24));
#endif
                if (s & (1 << j))
                  {
                        C(code, i, j,  0) = sizeof(WS_T) * (((4 * i + j + 15) & 31) - 16);
                        C(code, i, j, 24) = sizeof(WS_T) * (((4 * i + j -  1) & 31) - 16);
                  }
                else
                  {
                        C(code, i, j,  0) = sizeof(WS_T) * (((4 * i + j -  1) & 31) - 16);
                        C(code, i, j, 24) = sizeof(WS_T) * (((4 * i + j + 15) & 31) - 16);
                  }
                C(code, i, j, 12) = sizeof(WS_T) * (((4 * i + j +  7) & 31) - 16);
                C(code, i, j, 36) = sizeof(WS_T) * (((4 * i + j + 23) & 31) - 16);
#if DEBUG>=2
                //printf(" => %+3d:%+3d\n",
                  printf(" => %08lX:%08lX\n",
                                 C(code, i, j,  0),
                                 C(code, i, j, 24));
#endif
                }
        }
}

/***************************************************************
 *
 *      IyR[hđWJ
 *
 *      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)
{
#ifndef USE_MMX
  *pc++ = 0x66;
#endif
  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,
                int ofs)
{
#ifndef USE_MMX
  *pc++ = 0x66;
#endif
  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;
        }
}

/***************************************************************
 *
 *      ^Śçę˝ŽđđÍE˝ßśŹ
 *
 *      ^               ćŞĹč
 *      $               öĹč
 *      ?               CÓĚ1ś
 *      *               CÓĚ0śČă
 *      &               ĺŹćĘiVAO[vÉgíę˝ęAcapitalize
 *      ()              O[vť
 *      \s              or
 *      \1              ęvľ˝O[v(ŔĚ)
 *      $(fn)   eLXgđWJ(O[vÍNXĆľÄľíęé)
 *
 *                      ČşANXWJĚ^L
 *      [A-Z]   śNXč` ^ Írź
 *      {}              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--;
        }

  /* ęśĂÂWJ */
  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 == '[')
                {
                  /* NXđÜĆßé */
                  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 == ']');

                  /* }bvłę˝mŠç˝ßđśŹˇé */
                  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 */
                                                           sizeof(WS_T) * ((64 * ofs + j) + 32 - 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 */
                                                 sizeof(WS_T) * ((64 * ofs + c) + 32 - 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;

  /* t@CđÇÝŢ
         ąĚĹĹÍč˛ŤĹ 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 ^[QbgĚTCYđ`FbN */
  if (sz == TARGET_SIZ)
        {
          /* g[NĚgo[X */
          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, ">ćčăëĚ^[Qbg<%s(ry>ÍIh\n",
                          ds);
          *pe = 0;
        }

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

  /* JčÉ parse */
  expr = expr_buf;
  while (expr[0])
        {
          char const *p;
          int i;

          /* ŞĚ Whitespace đÇÝňÎˇ */
          while (isspace(expr[0]))
                expr++;

          if (!expr[0])
                break;

          /* g[NđŘčoˇ */
          for (p = expr; expr[0] && !isspace(expr[0]); expr++)
                ;

          /* WJˇé */
          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,
                                 sizeof(WS_T) * (31 - 16));
}

static
unsigned
usec()
{
#if !defined(WIN32)
  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
}

/***************************************************************
 *
 *      C[vĆŠ
 *
 */

/* č */
#if N_STRIDE == 7
static SLICE const sk6[N_STRIDE] =
{
  {0xAAAAAAAAUL, 0xAAAAAAAAUL, 0xAAAAAAAAUL, 0xAAAAAAAAUL},
  {0xCCCCCCCCUL, 0xCCCCCCCCUL, 0xCCCCCCCCUL, 0xCCCCCCCCUL},
  {0xF0F0F0F0UL, 0xF0F0F0F0UL, 0xF0F0F0F0UL, 0xF0F0F0F0UL},
  {0xFF00FF00UL, 0xFF00FF00UL, 0xFF00FF00UL, 0xFF00FF00UL},
  {0xFFFF0000UL, 0xFFFF0000UL, 0xFFFF0000UL, 0xFFFF0000UL},
  {0x00000000UL, 0xFFFFFFFFUL, 0x00000000UL, 0xFFFFFFFFUL},
  {0x00000000UL, 0x00000000UL, 0xFFFFFFFFUL, 0xFFFFFFFFUL},
};
#elif N_STRIDE == 6
static SLICE const sk6[N_STRIDE] =
{
  {0xAAAAAAAAUL, 0xAAAAAAAAUL},
  {0xCCCCCCCCUL, 0xCCCCCCCCUL},
  {0xF0F0F0F0UL, 0xF0F0F0F0UL},
  {0xFF00FF00UL, 0xFF00FF00UL},
  {0xFFFF0000UL, 0xFFFF0000UL},
  {0x00000000UL, 0xFFFFFFFFUL},
};
#endif

#ifdef WIN32
typedef int (__fastcall *CRYPT64_PP)(ALU_T const *k, ALU_T *lr);
#endif

ALIGN_PREFIX(16) struct KEY key64 ALIGN_SUFFIX(16);
ALIGN_PREFIX(16) struct PARAM param64 ALIGN_SUFFIX(16);

int
main(int argc, char *argv[])
{
  int i, j;
  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];

#ifdef WIN32
  HANDLE h;
#endif

#ifndef __GNUC__
  CRYPT64_PP d_crypt64;
#endif

#if 0
  if (argc < 2)
        {
          fprintf(stderr, "ŽŤÚńĘ\n");
          return 1;
        }
#endif

  assert((1 << N_STRIDE) == N_ALU * ALU_BITS);

  /* t[16] ÍAŕZĹgpˇéAall 1 ŞüÁÄ˘é */
  for (i = 0; i < N_ALU; i++)
        param64.t[16].a[i] = -1;

  /* ĹčL[ĚRs[ */
  for (i = 0; i < N_STRIDE; 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đÁĄľČ˘ęÍAR[hĚćđ
         writable ĚćÉWJľČÄŕć˘B
         [XXX] OSÉćÁÄÍA&ŔsÂ\ĚćđępĚT[BXĹ
         ćžľČŻęÎČçČ˘ŕĚŕ éŠŕľęČ˘ĚĹAÓ */
#ifdef WIN32
  h = CreateFileMapping(INVALID_HANDLE_VALUE,
                                                NULL,
                                                PAGE_EXECUTE_READWRITE,
                                                0, 0x20000000,
                                                NULL);
#ifndef FILE_MAP_EXECUTE
#define FILE_MAP_EXECUTE SECTION_MAP_EXECUTE    /* XXX cygwin */
#endif
  if (SUCCEEDED(h))
        code = (signed char *)MapViewOfFile(h,
                                                                                FILE_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

  /* ŞmŰĹŤÄ˘Č˘ęĚ˘ńżŤÎô */
  if (code == NULL)
        code = (signed char *)malloc(crypt64_end - crypt64_sta + 1024 * 1024);
  assert(code != NULL);

  /* Prologue đWJ */
  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);

  /* L[Ěúť */
  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(!((ptrdiff_t)&key64 & (sizeof(WS_T) - 1)));
  assert(!((ptrdiff_t)&param64 & (sizeof(WS_T) - 1)));

  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;
  /* Tő[vžźÁĆ */
  for (;;)
        {
          int32_t cnt;
          int k, kk;

          /* ŽĚZbg */
          for (i = 0; i < 8; i++)
                {
                  key_set64(&key64, i, key[i], key[i] ^ okey[i], 0);
                  okey[i] = key[i];
                }

          /* Ü¸Í 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", (int)cnt);
                }
          /* XXX č˛ŤĚ˝ßA[NÉÍÝoÄ˘é2rbgđĆˇ */
          for (i = 0; i < N_ALU; i++)
                param64.t[0].a[i] = param64.t[1].a[i] = 0;

          /* qbgľ˝ĆŤĚ */
          for (kk = 0; kk < N_ALU; kk++)
                {
                  ALU_T t;

                  t = param64.t[31].a[kk];
                  if (!t)
                        continue;

                  for (k = 0; k < ALU_BITS; k++)
                        {
                          char hash[16];
                          unsigned char buf[32];

                          if (!(t & ((ALU_T)1 << k)))
                                continue;

                          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] & ((ALU_T)1 << k));
                                  hash[i - 1] = c["./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"];
                                }
                          hash[10] = 0;

                          memcpy(buf, key, 32);
                          buf[8] = buf[9] = 0;
                          buf[7] = (buf[7] & -(1 << N_STRIDE) & 0x7F) + ALU_BITS * 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 << N_STRIDE) * (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 */