home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume10 / cbw / part04 / autotri.c next >
Encoding:
C/C++ Source or Header  |  1987-06-16  |  7.4 KB  |  367 lines
  1. /*
  2.  * Automatic guessing based on trigrams.
  3.  *
  4.  * Bob Baldwin, January 1985.
  5.  */
  6.  
  7. #include    <stdio.h>
  8. #include    <math.h>
  9. #include    "window.h"
  10. #include    "terminal.h"
  11. #include    "layout.h"
  12. #include    "specs.h"
  13. #include    "cipher.h"
  14. #include    "autotri.h"
  15.  
  16.  
  17. #define    DEBUGP    FALSE        /* Perm building */
  18. #define    DEBUGB    FALSE        /* Best guess */
  19.  
  20. #define    ATRLABEL1  \
  21. "Auto Trigram, max SD: %4.2f total: %d wire: %d -- Please Wait"
  22. #define    ATRLABEL2  \
  23. "Auto Trigram, max SD: %4.2f total: %d wire: %d -- Done"
  24. #define    ATRHELP         "F3 enters guess, ^G undoes it."
  25.  
  26.  
  27. extern    char    mcbuf[];
  28. extern    ecinfo    gecinfo;
  29. extern    atrdraw(), atrfirst(), atrenter(), atrundo();
  30.  
  31. /* Gloabal State. */
  32. char    *trigramstats;        /* Filename for statistics. */
  33. atrinfo    gatrinfo;
  34. keyer    atrktab[] = {
  35.         {CACCEPT, atrenter},
  36.         {CUNDO, atrundo},
  37.         {CGO_UP, jogup},
  38.         {CGO_DOWN, jogdown},
  39.         {CGO_LEFT, jogleft},
  40.         {CGO_RIGHT, jogright},
  41.         {0, NULL},
  42.         };
  43.  
  44. /* Routine invoked by user to put up the equivalence class
  45.  * guessing window.
  46.  * The window is drawn empty, and then filled in with the guess.
  47.  * Return NULL if command completes ok.
  48.  */
  49. char    *atrguess(str)
  50. char    *str;            /* Command line */
  51. {
  52.     gwindow    *atr;
  53.     atrinfo    *atri;
  54.     ecinfo    *ecbi;
  55.     int        *dbsperm;
  56.     int        i, c;
  57.     int        classpos;
  58.     int        x, y;
  59.  
  60.     atr = &gbstore;
  61.     atri = &gatrinfo;
  62.     dbsperm = refperm(dbsgetblk(&dbstore));
  63.     atr_init(mcbuf, dbsperm, atri);
  64.     ecbi = atri->eci;
  65.     atri->min_total_chars = 123;
  66.     atri->min_wire_chars = 456;
  67.  
  68.     if ((i = sscanf(str, "%*[^:]: %f %*[^:]: %d %*[^:]: %d",
  69.         &atri->max_score, &atri->min_total_chars,
  70.         &atri->min_wire_chars)) != 3)  {
  71.             return("Could not parse all three arguments.");
  72.         }
  73.  
  74.     gbsswitch(atr, ((char *) atri), atrktab, atrfirst, wl_noop, atrdraw);
  75.  
  76.     sprintf(statmsg, ATRLABEL1,
  77.             atri->max_score, atri->min_total_chars, atri->min_wire_chars);
  78.     gblset(&gblabel, statmsg);
  79.     atrdraw(atr);
  80.     fflush(stdout);
  81.  
  82.     atr_autoguess(atri);
  83.     decode(ecbi->ciphertext, ecbi->plaintext, ecbi->perm);
  84.  
  85.     sprintf(statmsg, ATRLABEL2,
  86.             atri->max_score, atri->min_total_chars, atri->min_wire_chars);
  87.     gblset(&gblabel, statmsg);
  88.     atrdraw(atr);
  89.  
  90.     return(NULL);
  91. }
  92.  
  93.  
  94. /*  (re) Draw the window.
  95.  */
  96. atrdraw(atr)
  97. gwindow    *atr;
  98. {
  99.     int            i;
  100.     int            row, col;
  101.     atrinfo        *atri;
  102.     ecinfo        *ecbi;
  103.  
  104.     atri = ((atrinfo *) atr->wprivate);
  105.     ecbi = atri->eci;
  106.     row = 1;
  107.     col = 1;
  108.  
  109.     for (i = 0 ; i < BLOCKSIZE ; i++)  {
  110.         if (i%LINELEN == 0) {
  111.             wl_setcur(atr, gbspos2row(i), gbspos2col(i));
  112.             }
  113.         plnchars(1, char2sym(ecbi->plaintext[i]));
  114.         }
  115.  
  116.     for (i = gbspos2row(BLOCKSIZE) ; i <= GBHEIGHT ; i++) {
  117.         wl_setcur(atr, i, 1);
  118.         plnchars(LINELEN, ' ');
  119.         }
  120.  
  121.     for (i = 1 ; i <= GBHEIGHT ; i++) {
  122.         wl_setcur(atr, i, LINELEN+1);
  123.         plnchars(atr->wwidth - LINELEN, ' ');
  124.         }
  125.  
  126.     wl_setcur(atr, row, col);
  127. }
  128.  
  129.  
  130. /* First time cursor enters window.
  131.  */
  132. atrfirst(atr, row, col)
  133. gwindow    *atr;
  134. int            row, col;
  135. {
  136.     usrhelp(&user, ATRHELP);
  137.     wl_setcur(atr, row, col);
  138. }
  139.  
  140.  
  141. /* Enter the guess into the decryption block.
  142.  */
  143. atrenter(atr)
  144. gwindow    *atr;
  145. {
  146.     atrinfo        *atri;
  147.  
  148.     atri = ((atrinfo *) atr->wprivate);
  149.     dbsmerge(&dbstore, atri->eci->perm);
  150.     wl_rcursor(atr);
  151. }
  152.  
  153.  
  154. /* Undo the last guess.
  155.  */
  156. atrundo(atr)
  157. gwindow    *atr;
  158. {
  159.     dbsundo(&dbstore);
  160.     wl_rcursor(atr);
  161. }
  162.  
  163.  
  164. /* Fill in auto-trigram info from given ciphertext block.
  165.  * The filter parameters are not set by this routine.
  166.  */
  167. atr_init(cipher, perm, atri)
  168. char    cipher[];
  169. int        perm[];
  170. atrinfo    *atri;
  171. {
  172. extern    int    *trig_loaded;
  173.     int        i;
  174.  
  175.     atri->eci = &gecinfo;
  176.     if (!trig_loaded)
  177.         load_tri_from(trigramstats);
  178.     ec_init(cipher, perm, atri->eci);
  179.     atr_guess_init(atri);
  180. }
  181.  
  182.  
  183. /* Per guess initialization.
  184.  */
  185. atr_guess_init(atri)
  186. atrinfo    *atri;
  187. {
  188.     atri->best_trigram = NULL;
  189.     atri->best_score = 10.0;
  190.     atri->gcount = 0;
  191.     atri->total_score = 0;
  192.     atri->best_pvec[0] = NONE;
  193.     atri->best_permvec[0].x = NONE;
  194. }
  195.  
  196.  
  197.  
  198. /* Score a trigram at a given position.
  199.  * It also looks in atri for filtering parameters (total number
  200.  * of chars must not be less than min_total_chars, and the minimum number
  201.  * of chars deduced per wire must not be less than min_wire_chars).
  202.  * This routine fills in permvec and pvec.
  203.  * Returns -1.0 if guess is unacceptable.
  204.  */
  205. float    atr_score(atri, trigent, pos, permvec, pvec)
  206. atrinfo        *atri;
  207. trig_ent    *trigent;
  208. int            pos;
  209. perment        permvec[];
  210. int            pvec[];
  211. {
  212.     int        length;
  213.     int        i, x, y;
  214.     int        ccount;
  215.     int        added;
  216.     extern    float    logvar;
  217.     float    score;
  218.     ecinfo    *eci;
  219.     int        butfirst;
  220.     int        butlast;
  221.  
  222.     for (length = 0 ; trigent->trigram[length] != 0 ; length++);
  223.     eci = atri->eci;
  224.     added = permvec_from_string(atri->eci, trigent->trigram, pos, permvec);
  225.     if (added < 0)  return(-1.0);
  226.  
  227.     butfirst = pos;
  228.     butlast = pos + length -1;
  229.     ccount = 0;
  230.  
  231.     for (i = 0 ; i < PERMSZ  &&  permvec[i].x != NONE ; i++)  {
  232.         if (ccount >= BLOCKSIZE-1)  break;
  233.         x = permvec[i].x;
  234.         y = permvec[i].y;
  235. /*        added = decode_wire_but(eci, x, y, &pvec[ccount], -1, -1);*/
  236.         added = decode_wire_but(eci, x, y, &pvec[ccount], butfirst, butlast);
  237.         if (added < 0)  {
  238.             ccount = 0;
  239.             break;
  240.             }
  241.         if (added < atri->min_wire_chars)  {
  242.             ccount = 0;
  243.             break;
  244.             }
  245.         ccount += added;
  246.         }
  247.     pvec[ccount] = -1;
  248.  
  249.     if (ccount <= 0)  return(-1.0);
  250.     if (ccount < atri->min_total_chars)  return(-1.0);
  251.  
  252.     score = pvec_1score(pvec);
  253.     if (score < 0.0)  return(-1.0);
  254. /*
  255.     score = exp(-(score * score) / 2.0);
  256.     score = score / sqrt(2*PI*logvar/ccount);
  257.     score = score * trigent->prob;
  258. */
  259.     return(score);
  260. }
  261.  
  262.  
  263. /* Select the best trigram for a given position.
  264.  * Returns pointer to trigram string, or NULL.
  265.  * Fills in atri with additional information.
  266.  * Filtering parameters are in atri.
  267.  */
  268. char    *atr_best(atri, pos)
  269. atrinfo    *atri;
  270. int        pos;
  271. {
  272.     int        tgram;
  273.     float    score;
  274.     perment    permvec[PERMSZ];
  275.     int        pvec[BLOCKSIZE+1];
  276. #if DEBUGB
  277.     char    str[BLOCKSIZE+1];
  278. #endif
  279.  
  280.     atr_guess_init(atri);
  281.  
  282.     for (tgram = 0 ; trig_tab[tgram].trigram != NULL ; tgram++)  {
  283.         score = atr_score(atri, &trig_tab[tgram], pos, permvec, pvec);
  284.         if (score < 0.0)  continue;
  285.         atri->total_score += score;
  286.         atri->gcount++;
  287.         if (score < atri->best_score) {
  288.             atri->best_score = score;
  289.             atri->best_trigram = trig_tab[tgram].trigram;
  290.             pvec_copy(pvec, atri->best_pvec);
  291.             permvec_copy(permvec, atri->best_permvec, PERMSZ);
  292.             }
  293.         }
  294.  
  295. #if DEBUGB
  296.     if (atri->best_score < atri->max_score) {
  297.         printf("\nTrigram '%s' at %d", atri->best_trigram, pos);
  298.         pvec2str(str, atri->best_pvec);
  299.         printf(" deduces '%s'", str);
  300.         printf(" which scores as %g", atri->best_score);
  301.         printf(".\n");
  302.         }
  303. #endif
  304.  
  305.     if (atri->best_score < atri->max_score)
  306.         {return(atri->best_trigram);}
  307.     else
  308.         {return(NULL);}
  309. }
  310.  
  311.  
  312. /* Merge the given permvector into the permutation table.
  313.  * Return ERROR if there is a conflict, otherwise TRUE.
  314.  */
  315. int    accept_permvec(atri, permvec)
  316. atrinfo    *atri;
  317. perment    permvec[];
  318. {
  319.     int        i, x, y;
  320.     ecinfo    *ecbi;
  321.  
  322.     ecbi = atri->eci;
  323.     for (i = 0 ; i < PERMSZ  &&  permvec[i].x != NONE ; i++)  {
  324.         x = MODMASK & permvec[i].x;
  325.         y = MODMASK & permvec[i].y;
  326.         if (perm_conflict(ecbi->perm, x, y)) {
  327. #if DEBUGP
  328.             printf("CONFLICT trying to wire %d to %d.\n", x, y);
  329. #endif
  330.             return(ERROR);
  331.             }
  332.         }
  333.  
  334.  
  335.     /* Now know that there are no conflicts. */
  336.     for (i = 0 ; i < PERMSZ  &&  permvec[i].x != NONE ; i++)  {
  337. #if DEBUGP
  338.         printf("ACCEPTING wiring of %d to %d.\n", x, y);
  339. #endif
  340.         x = MODMASK & permvec[i].x;
  341.         y = MODMASK & permvec[i].y;
  342.         ecbi->perm[x] = y;
  343.         ecbi->perm[y] = x;
  344.         }
  345.  
  346.     return(TRUE);
  347. }
  348.  
  349.  
  350.  
  351. /* Perform automatic guessing given a set of
  352.  * filter parameters in an atrinfo structure.
  353.  */
  354. atr_autoguess(atri)
  355. atrinfo    *atri;
  356. {
  357.     int        pos;
  358.     char    *trigram;
  359.  
  360.     for (pos = 0 ; pos < BLOCKSIZE ; pos++) {
  361.         trigram = atr_best(atri, pos);
  362.         if (trigram != NULL) {
  363.             accept_permvec(atri, atri->best_permvec);
  364.             }
  365.         }
  366. }
  367.