home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume10 / cbw / part05 / knit.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-06-17  |  10.5 KB  |  504 lines
  1. /*
  2.  * Use serveral mostly solved blocks to solve the knitting equation
  3.  * and deduce the rotor and reflector wirings.
  4.  *
  5.  * Robert W. Baldwin, December 1984.
  6.  */
  7.  
  8.  
  9. #include    <stdio.h>
  10. #include    "window.h"
  11. #include    "terminal.h"
  12. #include    "layout.h"
  13. #include    "specs.h"
  14.  
  15.  
  16. extern    char    gcbuf[];        /* All guess displays use same buffers. */
  17. extern    int        gpbuf[];
  18. extern    int        gperm[];
  19.  
  20.  
  21. #define KNTHELP    "F2 = next guess, F3 = enter guess, ^G = Undo enter."
  22. #define STARTMSG "Knitting from %d to %d.   Known Zee: %d of 256."
  23. #define GUESSMSG "guesscount = %d, xi=%d, yi=%d.   Known Zee: %d of 256."
  24. #define UNDOMSG  "Undone.  Current known Zee: %d of 256"
  25. #define    BIG        1000        /* Size of try stack in kntadvance(). */
  26.  
  27.  
  28. /* Pack and unpack two bytes into an integer. */
  29. #define pack(x,y)        (((x&0377)<<8) + y)
  30. #define unpack(x,y,v)    tmpv = v; x = ((tmpv>>8)&0377);  y = (tmpv&0377);
  31.  
  32.  
  33. /* Keystroke handler table. */
  34.  
  35. extern    int    kntadvance();
  36. extern    kntundo();
  37. extern    kntnextg();
  38. extern    kntenter();
  39.  
  40. keyer    kntktab[] = {
  41.         {CNEXTGUESS, kntnextg},
  42.         {CACCEPT, kntenter},
  43.         {CUNDO, kntundo},
  44.         {CGO_UP, jogup},
  45.         {CGO_DOWN, jogdown},
  46.         {CGO_LEFT, jogleft},
  47.         {CGO_RIGHT, jogright},
  48.         {0, NULL},
  49. };
  50.  
  51.  
  52.  
  53. /* Private data structure for guess blocks. */
  54.  
  55. #define    kntinfo        struct    xkntinfo
  56. struct    xkntinfo    {
  57.         char    *cbuf;        /* The cipher block. */
  58.         int        *pbuf;        /* The derived guess plaintext, -1 = none. */
  59.         int        *perm;        /* Permutation of block highbnum+1. */
  60.         int        xindex;        /* Starting position of next x guess. */
  61.         int        yindex;        /* Starting position of next y guess. */
  62.         int        *zee;        /* Knitting matrix. */
  63.         int        *zeeinv;    /* Its inverse. */
  64.         int        *ustkp;        /* Undo stack pointer. */
  65.         int        *savedustkp;    /* Undo stack pointer. */
  66.         int        *undostk;    /* Undo stack. */
  67.         int        lowbnum;    /* Block number of lowest source. */
  68.         int        highbnum;    /* Block number of highest source. */
  69.         int        min_show;    /* Smallest count to show. */
  70.         };
  71.  
  72.  
  73. /* Private buffers. */
  74. int        kzee[BLOCKSIZE+1];
  75. int        kzeeinv[BLOCKSIZE+1];
  76. int        kustk[BLOCKSIZE+1];
  77.  
  78. kntinfo    kntprivate;
  79.  
  80. int        kntinit    = FALSE;
  81.  
  82.  
  83. extern    kntdraw(), kntfirst();        /* Defined below. */
  84.  
  85.  
  86. /* This routine is called by the user command to clear the zee matrix.
  87.  */
  88. char    *clearzee(str)
  89. char    *str;        /* Command line */
  90. {
  91.     int        i;
  92.     kntinfo    *knti;
  93.  
  94.     knti = &kntprivate;
  95.     initknt();
  96.     kntclrzee(knti);
  97.  
  98.     if (&kntprivate == ((kntinfo *) gbstore.wprivate)) {
  99.         for (i = 0 ; i < BLOCKSIZE ; i++)  {
  100.             knti->perm[i] = -1;
  101.             }
  102.         decode(knti->cbuf, knti->pbuf, knti->perm);
  103.         sprintf(statmsg, GUESSMSG,
  104.                 0, knti->xindex, knti->yindex, zeecount(knti));
  105.         gblset(&gblabel, statmsg);
  106.         wl_draw(&gbstore);
  107.         }
  108.  
  109.     wl_rcursor(&user);
  110.     return(NULL);
  111. }
  112.  
  113.  
  114.  
  115. /* This routine is called to set up the guess block window
  116.  * to be used for guessing the zee matrix.
  117.  * It can be directly invoked by the command interpreter.
  118.  * Set up dbstore to show the block after the last block
  119.  * the the user says to consider complete.
  120.  */
  121. char    *kntguess(str)
  122. char    *str;        /* Command line */
  123. {
  124.     int        i;
  125.     int        from,to;
  126.     gwindow    *knt;
  127.     kntinfo    *knti;
  128.  
  129.     knt = &gbstore;
  130.     knti = &kntprivate;
  131.     initknt();
  132.  
  133.     if (!kntinit) {
  134.         kntinit = TRUE;
  135.         kntclrzee(knti);
  136.         }
  137.  
  138.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  139.         knti->perm[i] = -1;
  140.         }
  141.  
  142.     from = to = 0;
  143.     if ((i = sscanf(str,"%*[^:]: %d %*[^:]: %d %*[^:]: %d",
  144.                     &from, &to, &knti->min_show)) != 3) {
  145.         return("Could not parse all arguments.");
  146.         }
  147.     else {
  148.         if (to <= from)
  149.             return("To: must be less than From:");
  150.         }
  151.     
  152.     dbssetblk(&dbstore, to+1);
  153.     if (!fillcbuf(to+1, knti->cbuf)) {
  154.         return("Bad to: value");
  155.         }
  156.     decode(knti->cbuf, knti->pbuf, knti->perm);
  157.     knti->xindex = 0;
  158.     knti->yindex = 0;
  159.     knti->lowbnum = from;
  160.     knti->highbnum = to;
  161.  
  162.     gbsswitch(knt,((char *) knti), kntktab, kntfirst, wl_noop, kntdraw);
  163.     sprintf(statmsg, STARTMSG, from, to, zeecount(knti));
  164.     gblset(&gblabel, statmsg);
  165.     kntdraw(knt);
  166.  
  167.     wl_setcur(knt, 1, 1);
  168.     return(NULL);
  169. }
  170.  
  171.  
  172.  
  173. /* Clear the zee permutation and update any display info.
  174.  */
  175. kntclrzee(knti)
  176. kntinfo    *knti;
  177. {
  178.     int        i;
  179.  
  180.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  181.         knti->zee[i] = -1;
  182.         knti->zeeinv[i] = -1;
  183.         }
  184. }
  185.  
  186.  
  187. /* Compute the next successful guess of a wiring of ZEE.
  188.  * Show it to the user for acceptance/rejection.
  189.  */
  190. kntnextg(knt)
  191. gwindow    *knt;
  192. {
  193.     int        guesscnt;
  194.     kntinfo    *knti;
  195.     knti = ((kntinfo *) knt->wprivate);
  196.  
  197.     kntclrlast(knti);
  198.     while (TRUE) {
  199.         guesscnt = kntadvance(knti);
  200.         if ((guesscnt == 0) || (guesscnt >= knti->min_show))  break;
  201.         kntclrlast(knti);
  202.         }
  203.     if (guesscnt == 0)  {
  204.         gblset(&gblabel, "No more guesses");
  205.         return;
  206.         }
  207.     decode(knti->cbuf, knti->pbuf, knti->perm);
  208.  
  209.     sprintf(statmsg, GUESSMSG,
  210.             guesscnt, knti->xindex, knti->yindex, zeecount(knti));
  211.     gblset(&gblabel, statmsg);
  212.     kntdraw(knt);
  213. }
  214.  
  215.  
  216.  
  217. /* Clear last guess in zee, zeeinv, perm.
  218.  * Note that perm only holds the results of the last guess.
  219.  */
  220. kntclrlast(knti)
  221. kntinfo    *knti;
  222. {
  223.     int        tmpv;    /* For unpack. */
  224.     int        x,y;
  225.     int        i;
  226.  
  227.     while (knti->ustkp > knti->undostk)  {
  228.         unpack(x, y, *(--(knti->ustkp)));
  229.         knti->zee[x] = -1;
  230.         knti->zeeinv[y] = -1;
  231.         }
  232.     knti->ustkp = knti->savedustkp = knti->undostk;
  233.         
  234.     for (i = 0 ; i < BLOCKSIZE ; i++) {
  235.         knti->perm[i] = -1;
  236.         }
  237. }
  238.  
  239.  
  240.  
  241. /* Advance to the next acceptable guess at a wiring for Zee.
  242.  * This modifies zee, zeeinv, and perm.  Perm only contains the
  243.  * info derived from this guess, while zee and zeeinv accumulate
  244.  * information from all preceeding accepted guesses.
  245.  * Returns the number of guesses that we derived from the initial one.
  246.  * If out of acceptable guesses, returns 0.
  247.  * Perm must be cleared before calling this.
  248.  */
  249. int    kntadvance(knti)
  250. kntinfo    *knti;
  251. {
  252.     int        guesscount;
  253.     int        i;
  254.     int        tmpv;        /* For unpack. */
  255.     int        x,y;
  256.     int        tx,ty;
  257.     int        u,v;
  258.     int        tu,tv;
  259.     int        *a2;        /* The permutation as in u = A2 x */
  260.     int        *a1;        /* The permutation as in v = A1 y */
  261.     int        *propp;        /* Temp for undo stack propagation. */
  262.     int        *highperm;    /* Perm used to derive next perm. */
  263.     int        trycount;    /* Size of trystk. */
  264.     int        *tstkp;        /* Stack of guesses to check. */
  265.     int        trystk[BIG];
  266.  
  267. /* kntadvance(knti)
  268.  */
  269.     guesscount = 0;        /* In case loop body never executes. */
  270.  
  271.     if (knti->xindex >= BLOCKSIZE)  return(0);
  272.     if (knti->yindex >= BLOCKSIZE)  {
  273.         knti->yindex = 0;
  274.         knti->xindex++;
  275.         }
  276.  
  277.     for (x = knti->xindex ; x < BLOCKSIZE ; x++) {
  278.         if (knti->zee[x] != -1)  {
  279.             knti->yindex = 0;
  280.             continue;
  281.             }
  282.         for (y = knti->yindex ; y < BLOCKSIZE ; y++) {
  283.             if (knti->zeeinv[y] != -1)  continue;
  284.             guesscount = 0;
  285.             tstkp = trystk;                    /* Assume ustkp == undostk. */
  286.             trycount = 0;
  287.             *(tstkp++) = pack(x,y);
  288.             trycount++;
  289.  
  290.             while (tstkp > trystk) {
  291.                 unpack(tx, ty, *(--tstkp));
  292.                 trycount--;
  293.                 if (knti->zee[tx] == -1 && knti->zeeinv[ty] == -1) {
  294.                     knti->zee[tx] = ty;
  295.                     knti->zeeinv[ty] = tx;
  296.                     *((knti->ustkp)++) = pack(tx,ty);
  297.                     guesscount++;
  298.                     for (i = knti->lowbnum ; (i+1) <= knti->highbnum ; i++) {
  299.                         a1 = refperm(i);
  300.                         a2 = refperm(i+1);
  301.                         tu = a2[tx];
  302.                         tv = a1[ty];
  303.                         if (tu != -1 && tv != -1 && trycount < BIG) {
  304.                             *(tstkp++) = pack(tu, tv);
  305.                             trycount++;
  306.                             }
  307.                         }
  308.                     }
  309.                 else if (knti->zee[tx] != ty
  310.                       || knti->zeeinv[ty] != tx) {        /* If conflict. */
  311.                         while (knti->ustkp > knti->undostk)  {
  312.                             unpack(tx, ty, *(--(knti->ustkp)));
  313.                             knti->zee[tx] = -1;
  314.                             knti->zeeinv[ty] = -1;
  315.                             guesscount--;
  316.                             }
  317.                         knti->ustkp = knti->undostk;
  318.                         goto nxtguess;
  319.                       }
  320.                 else continue;        /* Already know about it. */
  321.                 }
  322.  
  323.             knti->xindex = x;        /* Zee[x] = y was a good guess. */
  324.             knti->yindex = y+1;
  325.             propp = knti->ustkp;
  326.             highperm = refperm(knti->highbnum);
  327.             while (propp > knti->undostk) {  /* Update perm. */
  328.                 unpack(tx, ty, *(--propp));
  329.                 v = highperm[ty];
  330.                 if (v != -1  &&  (tmpv = knti->zeeinv[v]) != -1)  {
  331.                     knti->perm[tx] = tmpv;
  332.                     knti->perm[tmpv] = tx;
  333.                     }
  334.                 }
  335.             return (guesscount);
  336.             nxtguess: ;
  337.             }
  338.         knti->yindex = 0;
  339.         }
  340.  
  341.     knti->yindex = 0;
  342.     knti->xindex = 0;
  343.     return(guesscount);
  344. }
  345.              
  346.  
  347. /* Enter our current guess into the decryption block.
  348.  * Clear out the undo stack.
  349.  */
  350. kntenter(knt)
  351. gwindow    *knt;
  352. {
  353.     kntinfo    *knti;
  354.  
  355.     knti = ((kntinfo *) knt->wprivate);
  356.     knti->savedustkp = knti->ustkp;        /* If we change our mind. */
  357.     knti->ustkp = knti->undostk;
  358.     if (knti->highbnum+1 != dbsgetblk(&dbstore))
  359.         dbssetblk(&dbstore, knti->highbnum+1);
  360.     dbsmerge(&dbstore, knti->perm);
  361.     wl_rcursor(knt);
  362. }
  363.  
  364.  
  365. /* Undo the last guess.
  366.  */
  367. kntundo(knt)
  368. gwindow    *knt;
  369. {
  370.     kntinfo    *knti;
  371.  
  372.     knti = ((kntinfo *) knt->wprivate);
  373.     knti->ustkp = knti->savedustkp;
  374.     kntclrlast();
  375.     dbsundo(&dbstore);
  376.  
  377.     sprintf(statmsg, UNDOMSG, zeecount(knti));
  378.     gblset(&gblabel, statmsg);
  379.     wl_rcursor(knt);
  380. }
  381.  
  382.  
  383. /* Behavior when first enter the window.
  384.  * Put up a help message.
  385.  * Accept the cursor where it is.
  386.  */
  387. kntfirst(knt, row, col)
  388. gwindow    *knt;
  389. int        row,col;    /* Current coordinates. */
  390. {
  391.     usrhelp(&user, KNTHELP);
  392.     wl_setcur(knt, row, col);
  393. }
  394.  
  395.  
  396.  
  397. /* (re)Draw the window.
  398.  */
  399. kntdraw(knt)
  400. gwindow    *knt;
  401. {
  402.     int            i;
  403.     int            row, col;        /* Original row and column. */
  404.     kntinfo        *knti;
  405.  
  406.     knti = ((kntinfo *) knt->wprivate);
  407.     row = knt->wcur_row;
  408.     col = knt->wcur_col;
  409.  
  410.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  411.         if (i%LINELEN == 0) {
  412.             wl_setcur(knt, gbspos2row(i), gbspos2col(i));
  413.             }
  414.         plnchars(1, char2sym(knti->pbuf[i]));
  415.         }
  416.  
  417.     for (i = gbspos2row(BLOCKSIZE) ; i <= GBHEIGHT ; i++) {
  418.         wl_setcur(knt, i, 1);
  419.         plnchars(LINELEN, ' ');
  420.         }
  421.  
  422.     for (i = 1 ; i <= GBHEIGHT ; i++) {
  423.         wl_setcur(knt, i, LINELEN+1);
  424.         plnchars(knt->wwidth - LINELEN, ' ');
  425.         }
  426.  
  427.     wl_setcur(knt, row, col);
  428. }
  429.  
  430.  
  431. /* Return number of known wires in Zee.
  432.  * Max is 256.
  433.  */
  434. int    zeecount(knti)
  435. kntinfo    *knti;
  436. {
  437.     return(permcount(knti->zee));
  438. }
  439.  
  440.  
  441. /* Store Zee permutation on a file.
  442.  */
  443. storezee(fd)
  444. FILE    *fd;
  445. {
  446.     writeperm(fd, kzee);
  447. }
  448.  
  449.  
  450. /* Load the Zee permutation from a file.
  451.  * Update display if necessary.
  452.  */
  453. loadzee(fd)
  454. FILE    *fd;
  455. {
  456.     int        i;
  457.     kntinfo    *knti;
  458.  
  459.     knti = &kntprivate;
  460.     initknt();
  461.     kntinit = TRUE;
  462.     kntclrzee(knti);        /* Clear zeeinv */
  463.  
  464.     readperm(fd, kzee);    
  465.     for (i = 0 ; i < BLOCKSIZE ; i++) {
  466.         if (kzee[i] != -1)  {kzeeinv[kzee[i]] = i;}
  467.         }
  468.  
  469.     if (knti == ((kntinfo *) gbstore.wprivate)) {
  470.         for (i = 0 ; i < BLOCKSIZE ; i++)  {
  471.             knti->perm[i] = -1;
  472.             }
  473.         decode(knti->cbuf, knti->pbuf, knti->perm);
  474.         sprintf(statmsg, GUESSMSG,
  475.                 0, knti->xindex, knti->yindex, zeecount(knti));
  476.         gblset(&gblabel, statmsg);
  477.         wl_draw(&gbstore);
  478.         wl_setcur(&gbstore, 1, 1);
  479.         }
  480. }
  481.  
  482.  
  483. /* Set up all the pointers in kntprivate.
  484.  */
  485. initknt()
  486. {
  487.     int        i;
  488.     gwindow    *knt;
  489.     kntinfo    *knti;
  490.  
  491.     knt = &gbstore;
  492.     knti = &kntprivate;
  493.  
  494.     knti->zee = kzee;
  495.     knti->zeeinv = kzeeinv;
  496.  
  497.     knti->cbuf = gcbuf;
  498.     knti->pbuf = gpbuf;
  499.     knti->perm = gperm;
  500.  
  501.     knti->undostk = kustk;
  502.     knti->ustkp = knti->savedustkp = knti->undostk;
  503. }
  504.