home *** CD-ROM | disk | FTP | other *** search
/ rtsi.com / 2014.01.www.rtsi.com.tar / www.rtsi.com / OS9 / OSK / TELECOM / OSKBox.lzh / MAILBOX / CC / bsq.c < prev    next >
Text File  |  1987-10-04  |  33KB  |  857 lines
  1. /************************************************************************
  2.  * Binary file squeeze for packet transmission  Steve Ward W1GOH 1/86   *
  3.  * Version 2.0 2/20/86                                                  *
  4.  ************************************************************************
  5.  **  Copyright 1986 by W1GOH on bahalf of the Amateur Radio community. **
  6.  **   Unrestricted permission to use, copy, modify, extend, improve,   **
  7.  **          and build upon this program is hereby granted.            **
  8.  ************************************************************************
  9.  *                                                                      *
  10.  * Converts a binary file to ASCII, excluding "special" characters      *
  11.  *   which might cause trouble over ASCII transmission media (viz.      *
  12.  *   packet radio).  Does some data compression.                        *
  13.  *                                                                      *
  14.  * USAGE:                                                               *
  15.  *   bsq <options> file.ext [outname]                                   *
  16.  *      reads binary file.ext, writes file.bsq (or outname if specified)*
  17.  *   bsq <options> file.bsq [outname]                                   *
  18.  *      reads file.bsq, writes original file name (or outname)          *
  19.  *                                                                      *
  20.  *   <options> may include:                                             *
  21.  *      -b      Bootstrap mode.  Does simple bit-stuffing, no data      *
  22.  *              compression.  Output file suitable for simple BASIC pgm *
  23.  *      -o      Old format.  Writes a .BSQ file compatible with earlier *
  24.  *              versions of BSQ.                                        *
  25.  *                                                                      *
  26.  *  A trivial BASIC program suffices to decode files converted with     *
  27.  *      the -b option.  Although originally intended for bootstraping   *
  28.  *      the BSQ program over the air, it may be used routinely if       *
  29.  *      expedient.  However, the BASIC pgm is very primitive indeed.    *
  30.  *                                                                      *
  31.  *  This program is written in vanilla C, and should be easy to port.   *
  32.  *      Currently I have it running on VAX/UNIX and IBM PCs; I          *
  33.  *      encourage interested parties to port it to CPM and other        *
  34.  *      environments.                                                   *
  35.  *                                                                      *
  36.  ************************************************************************
  37.  *                                                                      *
  38.  * The encoding algorithm involves the following techniques:            *
  39.  *   (1) Basic bit-stuffing, breaking input stream of 8-bit binary bytes*
  40.  *       into an output stream of 6-bit printable ASCII chars.  Each    *
  41.  *       of the latter is relocated to printable range by adding 33 dec.*
  42.  *   (2) Data compression, which uses 28 of the remaining 30 printable  *
  43.  *       ASCII codes as "meta" characters abbreviating input byte       *
  44.  *       sequences.  My compression scheme is adapted from the TERSE    *
  45.  *       algorithm; it involves 2 identical FSMs (at sender & receiver, *
  46.  *       respectively) which cause meta chars to be defined in identical*
  47.  *       way at both ends on basis of communications history.  In       *
  48.  *       particular, each output step -- either of a bit-stuffed byte   *
  49.  *       or of a meta symbol -- causes a new meta symbol to be defined  *
  50.  *       as the PREVIOUS TWO output symbols.  The metasymbol to be      *
  51.  *       thus defined is selected via a deterministic LRU approximation,*
  52.  *       avoiding conflicts with active subnodes via a reference count. *
  53.  *   (3) A 29th character serves as a REPEAT code.  REPEAT followed by  *
  54.  *       a 6-bit count (relocated to ASCII per above) causes the last   *
  55.  *       INPUT symbol to be rescanned <count> times... thus if the      *
  56.  *       last input symbol was a meta symbol representing a 100-byte    *
  57.  *       string, the repeat sequence might expand to 6300 bytes.        *
  58.  *   (4) Additional compression hacks are envisioned for the remaining  *
  59.  *       character.  Watch this space.                                  *
  60.  *                                                                      *
  61.  * The bit-stuffing yields an output file 4/3 the size of the input,    *
  62.  * inflated further by (1) a header line and (2) CR/LFs at each output  *
  63.  * line.                                                                *
  64.  *                                                                      *
  65.  * BUGS:                                                                *
  66.  *   1. The program has suffered from a period of evolution, and needs  *
  67.  *      to be cleaned up somewhat.  Volunteers welcome.                 *
  68.  *   2. The algorithm is still the subject of sporadic hacking.  It     *
  69.  *      might change incompatibly, if I hit upon something significantly*
  70.  *      better.  Incompatibities are in theory detectable, however,     *
  71.  *      by virtue of a version number in .bsq file headers.             *
  72.  ************************************************************************
  73.  * Program history:                                                     *
  74.  *  12/24/85 SAW: First version working.                                *
  75.  *   1/1/86  SAW: Added data compression (v. 1.0)                       *
  76.  *   2/17/86 SAW: Cleaned up, implemented K1OJH's suggestion of output  *
  77.  *      to file named in header.  Also part number, nparts in header.   *
  78.  *      (v. 1.2)                                                        *
  79.  *   2/20/86 SAW: Improved data compression, by avoiding flushing the   *
  80.  *      bit-stuff pipeline on meta chars (uses buffer BinBuf for latter)*
  81.  *      Also "suspicious text" messages. (v. 2.0)                       *
  82.  ************************************************************************/
  83.  
  84. #include <stdio.h>
  85. #define VERSION 2               /* Version number, for file header      */
  86. char *ANode();                  /* Here for debugging only!             */
  87.  
  88. /************************************************************************
  89.  * POTENTIAL MACHINE/COMPILER DEPENDANCIES                              *
  90.  ************************************************************************/
  91. typedef unsigned char byte;
  92. typedef unsigned short ushort;
  93.  
  94. /************************************************************************
  95.  * Parameters & Globals                                                 *
  96.  ************************************************************************/
  97.  
  98. #define NTS     28              /* Number of definable nonterminals     */
  99. #define NNODES  NTS             /* Max nodes for data compression       */
  100.  
  101. #define ASCBITS 6               /* Bits per ASCII character.            */
  102. #define ASCODES (1<<ASCBITS)    /* number of codes for bitstuffing      */
  103. #define ASCBAS  041             /* Base char for code.                  */
  104. #define METABAS (ASCBAS+ASCODES)/* Base code for meta chars             */
  105. #define METARPT (METABAS+NTS)   /* Repeat code.                         */
  106.  
  107. int NNodes = NNODES;            /* Number of nodes used                 */
  108. char *from, to[100];            /* Source, destination file names       */
  109. char fname[100];                /* Name from .bsq file                  */
  110. FILE *in, *out;                 /* Input, output streams.               */
  111.  
  112. char    BFlag=0;                /* Bootstrap- mode                      */
  113. char    OldFlag=0;              /* Old format.                          */
  114.  
  115. typedef ushort NodeID;          /* Node identifier:                     */
  116.  
  117. #define ATOMIC(N) ((N)&0x8000)  /*  Atomic node... else internal.       */
  118. #define DATA(N)  ((N)&0xFF)     /*  Data from atomic node.              */
  119. #define UNUSED ((NodeID) 0xFFFF)/* Code for undefined node.             */
  120. #define MKATOM(D) ((D)|0x8000)  /* Make an atomic node, given index.    */
  121.  
  122. struct Node
  123.  {      NodeID Left, Right;     /* Inferiors.                           */
  124.         ushort Refs;            /* Reference count.                     */
  125.         ushort Size;            /* Total number of terminals            */
  126.         ushort Next, Prev;      /* LRU Chain.                           */
  127.         ushort Prefix;          /* List of nodes having this as Left    */
  128.         ushort Thread;          /* Above thread.                        */
  129.  } Nodes[NNODES];               /* The node database.                   */
  130.  
  131. NodeID  LRUHead;                /* Most recently used nonterminal.      */
  132. NodeID  Prefixes[256];          /* Prefix threads for terminals         */
  133.  
  134. #define NodeSize(N) ((ATOMIC(N)? 1:Nodes[N].Size))
  135.  
  136. #define COLUMNS 72              /* Number of chars/output line          */
  137. int     CheckColumns=COLUMNS;   /* Number of chars/line expected on inp */
  138. unsigned checksum;              /* Checksum of input bytes              */
  139. long     NBytes;                /* Bytes read/written                   */
  140. long     Length;                /* Target length of file.               */
  141. NodeID Previous = UNUSED;               /* For state machine.           */
  142.  
  143. #define BBSIZE  1024            /* Size of buffer for meta-chars --     */
  144. char BinBuf[BBSIZE];            /* Used to buffer meta-output whilst    */
  145. int BinN;                       /*   holding partial bit-stuff word.    */
  146. int Partials = 1;               /* FLAG: nonzero iff saving partials.   */
  147.  
  148. #define OutBin(bb) BinBuf[BinN++] = bb  /* Output a byte to BinBuf      */
  149.  
  150.  
  151. NodeInit()
  152.  {      register i, j;
  153.  
  154.         for (i=0; i<256; i++) Prefixes[i] = UNUSED;
  155.  
  156.         for (i=0; i<NNodes; i++)        /* Fix up node pool             */
  157.          { Nodes[i].Left = UNUSED;      /* Free node.                   */
  158.            Nodes[i].Refs = 0;           /* No references.               */
  159.            Nodes[i].Size = 0;
  160.            Nodes[i].Next = (i+1+NNodes)%NNodes;
  161.            Nodes[i].Prev = (i-1+NNodes)%NNodes;
  162.          }
  163.         LRUHead = 0;                    /* Head of LRU chain.           */
  164.         Previous = UNUSED;
  165.  }
  166.  
  167. /* Allocate & return a node, bumping ref counts of inferiors.
  168.  * Finds least recently used node whose ref count is zero.
  169.  * Ref cnt of returned node is zero.
  170.  */
  171.  
  172. NodeID NewNode(left, right)
  173.  NodeID left, right;
  174.  {      register struct Node *p;
  175.         int n, oldn, oldnn = -1;
  176.  
  177.         /* Show left, right as used FIRST, to prevent re-allocating.    */
  178.         if (!ATOMIC(left)) Nodes[left].Refs++;
  179.         if (!ATOMIC(right)) Nodes[right].Refs++;
  180.  
  181.         /* Follow LRU chain, looking for candidate to recycle.          */
  182.         for (oldn = n = Nodes[LRUHead].Prev; ; n = p->Prev)
  183.          { if (n == oldnn) Error("Node alloc!");/* "Can't happen!"      */
  184.            oldnn = oldn;
  185.            p = &Nodes[n];
  186.            if (p->Refs == 0)            /* Unused node?                 */
  187.             {   KillNode(n);            /* Yup, recycle it.             */
  188.                 break;
  189.             }
  190.          }
  191.  
  192.         p->Left = left;
  193.         p->Right = right;
  194.         p->Refs = 0;                    /* Presumably no superiors yet  */
  195.         p->Prefix = UNUSED;             /* No left superiors, yet       */
  196.         p->Size = NodeSize(left)+NodeSize(right);
  197.  
  198.         /* Splice onto proper Prefix thread:                            */
  199.         if (ATOMIC(left))
  200.                 { p->Thread = Prefixes[DATA(left)];
  201.                   Prefixes[DATA(left)] = n;
  202.                 }
  203.         else    { p->Thread = Nodes[left].Prefix;
  204.                   Nodes[left].Prefix = n;
  205.                 }
  206.  
  207.         Touch(n);                       /* Bring it to head of LRU chn  */
  208.         return n;
  209.  }
  210.  
  211. /* De-allocate a node:
  212.  */
  213. KillNode(n)
  214.  {      register struct Node *p;
  215.         register NodeID *nid;
  216.  
  217.         p = &Nodes[n];
  218.         if (p->Left == UNUSED) return;          /* Unallocated node.    */
  219.  
  220.         /* Splice out of prefix list.                                   */
  221.         if (ATOMIC(p->Left)) nid = &Prefixes[DATA(p->Left)];
  222.         else nid = &(Nodes[p->Left].Prefix);
  223.         for  (; *nid != UNUSED; nid = &(Nodes[*nid].Thread))
  224.          {      if (*nid == n)
  225.                         { *nid = p->Thread;
  226.                           break;
  227.                         }
  228.          }
  229.  
  230.         /* Deref inferior nodes.                                        */
  231.         if (!ATOMIC(p->Left)) Nodes[p->Left].Refs--;
  232.         if (!ATOMIC(p->Right)) Nodes[p->Right].Refs--;
  233.  
  234.         p->Left = p->Right = UNUSED;            /* Now nothings used.   */
  235.         p->Refs = 0;
  236.  }
  237.  
  238. /* "Touch" a nonterminal... ie, make it recent.
  239.  */
  240. Touch(n)
  241.  {      int prev, next;
  242.         register struct Node *p, *l;
  243.  
  244.         if (ATOMIC(n)) return;          /* Shouldnt happen, but ...     */
  245.  
  246.         p = &Nodes[n];                  /* To become head of chain.     */
  247.         Nodes[p->Prev].Next = p->Next;  /* Splice out node n.           */
  248.         Nodes[p->Next].Prev = p->Prev;
  249.  
  250.         l = &Nodes[LRUHead];            /* Current head of chain.       */
  251.         p->Prev = l->Prev;              /* Splice in n as new head.     */
  252.         p->Next = LRUHead;
  253.         Nodes[p->Prev].Next = n;
  254.         l->Prev = n;
  255.         LRUHead = n;
  256.  }
  257.  
  258. /* Drive the database state: call whenever a node is output.            */
  259. NodeOut(n)
  260.  NodeID n;
  261.  {
  262.         if (Previous != UNUSED)         /* Define a new node.           */
  263.                 { NodeID new;
  264.                   new = NewNode(Previous, n);
  265.                 }
  266.         Previous = n;
  267.  }
  268.  
  269. /* Lookahead Input routines:
  270.  */
  271.  
  272. byte ibuf[1024];                        /* Lookahead buffer             */
  273. short ibufbase = 0,                     /* Base index of buffer         */
  274.       ibufn = 0;                        /* Bytes in buffer.             */
  275.  
  276. #define INEOF ((!ibufn)&&(feof(in)))    /* Detect EOF on input.         */
  277.  
  278. Peek(n)                                 /* Returns -1 iff can't.        */
  279.  {      int nr;
  280.         register ch;
  281.  
  282.         while (ibufn <= n)
  283.          { if (n >= 1024) return -1;
  284.            if (feof(in)) return -1;     /* Can't read any more.         */
  285.            nr = (ibufbase+ibufn) & 1023;
  286.            while (!feof(in) && (ibufn < 1024))
  287.                 { if ((ch = getc(in)) == EOF) break;
  288.                   ibuf[nr++] = ch;
  289.                   nr &= 1023;
  290.                   ++ibufn;
  291.                 }
  292.          }
  293.         return 0xFF & ibuf[(n+ibufbase) & 1023];
  294.  }
  295.  
  296. /* Remove next n input chars from buffer:                               */
  297. Remove(n)
  298.  {      ibufbase = (ibufbase+n) & 1023;
  299.         ibufn -= n;
  300.  }
  301.  
  302.  
  303.  
  304.  
  305. NodeID  FindBest;
  306. int     FindSize;
  307.  
  308. /* Called with n=node, offset = next input symbol locn on match.
  309.  * Updates FindBest, FindSize to best (longest) match.
  310.  */
  311. MatchHit(n, offset)
  312.  {      NodeID thr;
  313.         register struct Node *p;
  314.  
  315.         p = &Nodes[n];
  316.         if (ATOMIC(n))
  317.          { if (!FindSize) { FindSize = 1; FindBest = n; }
  318.          }
  319.         else
  320.          { if (FindSize < p->Size) { FindSize = p->Size; FindBest = n; }
  321.            thr = p->Prefix;
  322.            FindRight(thr, offset);
  323.          }
  324.  
  325.  }
  326.  
  327. /* Follow a thread.  Find all matches of right inferior, calling MatchHit.
  328.  * Presumably, left nodes all match just fine.
  329.  */
  330.  
  331. FindRight(thr, offset)
  332.  {      register i;
  333.  
  334.         while (thr != UNUSED)
  335.          { if (i = AbMatch(offset, Nodes[thr].Right))
  336.                 MatchHit(thr, offset+i);
  337.            thr = Nodes[thr].Thread;
  338.          }
  339.  }
  340.  
  341.  
  342. /* Find longest applicable abbreviation.
  343.  * Leaves Best node in FindBest, its size in FindSize;
  344.  * Returns size of best abbreviation, or 0 iff none.
  345.  */
  346.  
  347. NodeID  AbBest;                 /* AbMatch return values: NodeID,       */
  348. int     AbSize;                 /* Size of node.                        */
  349.  
  350. Abbrev()
  351.  {      register i, j;
  352.  
  353.         if (((j = Peek(0)) == -1) ||            /* EOF.                 */
  354.             ((i = Prefixes[j]) == UNUSED))      /* Nothing there.       */
  355.                 return 0;                       /* Return failure.      */
  356.  
  357.         FindBest = UNUSED;
  358.         FindSize = 0;
  359.         FindRight(i, 1);                        /* Search for match.    */
  360.  
  361.         return FindSize;
  362.  }
  363.  
  364. /* Perform the recursive match.
  365.  * Returns results in AbBest, AbSize.
  366.  * Returns size, or 0 iff none.
  367.  * offset is position in input stream, n is node ID.
  368.  */
  369.  
  370. AbMatch(offset, n)
  371.  NodeID n;
  372.  {      register j;
  373.  
  374.         if (n == UNUSED) return 0;
  375.         if (ATOMIC(n))
  376.          { if (DATA(n) == Peek(offset))
  377.                 { AbBest = n;
  378.                   return AbSize = 1;
  379.                 }
  380.            return 0;
  381.          }
  382.  
  383.         if (j = AbMatch(offset, Nodes[n].Left))
  384.          { register k;
  385.            if (k = AbMatch(offset+j, Nodes[n].Right))
  386.                 { AbBest = n;
  387.                   return (AbSize = j+k);
  388.                 }
  389.          }
  390.         return 0;
  391.  }
  392.  
  393. /* Check for repeats.
  394.  * Returns size of repeat string (in bytes), or 0 iff none.
  395.  * Leaves repeat count in FindSize.
  396.  * Guarantees repeat count < 64.
  397.  */
  398. Repeat()
  399.  {      register size, i;
  400.  
  401.         if (Previous == UNUSED) return;
  402.         if (ATOMIC(Previous))           /* String of atoms?             */
  403.          { for (i=DATA(Previous), size=0; Peek(size) == i; size++)
  404.                 if (size >= 63) break;
  405.            return FindSize=size;
  406.          }
  407.         FindSize = 0;
  408.  
  409.         for (size=0; i = AbMatch(size, Previous);)
  410.          { size += i;
  411.            if (++FindSize >= 63) break;
  412.          }
  413.         return size;
  414.  }
  415.  
  416. /* Return pointer to directory-less file name:                          */
  417. char *BaseName(cc)
  418.  register char *cc;
  419.  {      register char *dd;
  420.         dd = cc;
  421.         for (;*cc;++cc) if ((*cc == '/') || (*cc == '\\')) dd = cc+1;
  422.         return dd;
  423.  }
  424.  
  425. char *extension(name)
  426.  char *name;
  427.  {      while (*name && (*name != '.')) name++;
  428.         return name;
  429.  }
  430.  
  431. main(argc, argv)
  432.  char **argv;
  433.  {      char *arg, argn, tobsq = 0;
  434.  
  435.         while ((argc>1) && (*(arg=argv[1]) == '-'))     /* OPTIONS      */
  436.           switch (*++arg)
  437.                 {
  438.                         case 'o':       OldFlag = 1; argv++; argc--;
  439.                                         Partials = 0;
  440.                                         continue;
  441.                         case 'b':       BFlag = 1; argv++; argc--; continue;
  442.                         default:        Error("Illegal option '%s'", argv[1]);
  443.                 }
  444.  
  445.         if ((argc < 2) || (argc > 3)) Usage();
  446.         from = argv[1];
  447.  
  448.  
  449.         if (!strcmp(extension(from), ".bsq"))
  450.          { if (argc > 2) strcpy(to, argv[2]);
  451.            tobsq = 0;
  452.          }
  453.         else
  454.          { if (argc > 2) strcpy(to, argv[2]);
  455.            else { strcpy(to, BaseName(from));
  456.                   strcpy(extension(to), ".bsq");
  457.                 }
  458.            tobsq = 1;
  459.          }
  460.  
  461.         NodeInit();
  462.  
  463.         /* Open input and output files.                                 *
  464.          * NB: Files must be read/written in BINARY.  If your C         *
  465.          * environment (eg Lattice MSDOS) requires some funny code to   *
  466.          * open files for binary I/O, do it here!                       */
  467.  
  468.         if (!(in = fopen(from, "r"))) Error("Can't read file %s", from);
  469.         if (!tobsq) RdHeader();
  470.  
  471.         if (!(out = fopen(to, "w"))) Error("Can't write file %s", to);
  472.  
  473.         Msg("W1GOH Binary SQueeze 2.0: %s -> %s\n", from, to);
  474.         if (tobsq) Squeeze();
  475.         else UnSqueeze();
  476.         return 0;
  477.  }
  478.  
  479.  
  480. Usage()
  481.  {      Error("Usage: bsq infile [outfile]\n");
  482.  }
  483.  
  484. /************************************************************************
  485.  *                                                                      *
  486.  * Actual conversion happens here.                                      *
  487.  *                                                                      *
  488.  * Algorithm:                                                           *
  489.  *   bytes 041 - 0xx are 6-bit data, bit-stuffed into output byte stream*
  490.  *   Each 8-bit output byte shifted into LastCh output fifo, whence     *
  491.  *    LastCh[0] is most recent byte, LastCh[1] next most recent, etc    *
  492.  *   Remaining 30 codes are META bytes, and cause output from defn      *
  493.  *    (besides flushing any accumulated partial byte if !Partials)      *
  494.  ************************************************************************/
  495.  
  496. /* File conversion: BINARY -> ASCII                                     */
  497.  
  498. Squeeze()
  499.  {      register ch, i;
  500.  
  501.         /* First, make space for a header:                              */
  502.         WrHeader();
  503.         crlf();
  504.  
  505.         NBytes = Length = 0;
  506.         AscInit();
  507.  
  508.         for (;;)
  509.          {
  510.            if (!BFlag && (BinN < (BBSIZE-3)))
  511.             {   int rsize=0, rcnt, asize=0;
  512.  
  513.                    if ((ch = Repeat()) && (FindSize > 1) && (ch > 4))
  514.                     { rsize = ch;
  515.                       rcnt = FindSize;
  516.                     }
  517.  
  518.                    asize = Abbrev();
  519.  
  520.                    if ((rsize-1) > asize)       /* Use the repeat??     */
  521.                     { if (!Partials)
  522.                        FlushStuff();            /* Flush stuff state.   */
  523.                       OutBin(METARPT-ASCBAS);   /* Use a meta char.     */
  524.                       OutBin(rcnt);             /* Repeat count.        */
  525.                       for (i=0; i<rsize; i++)
  526.                         { checksum += Peek(i);
  527.                         }
  528.                       Remove(rsize);            /* Flush input string.  */
  529.                       NBytes += rsize;
  530.                       continue;
  531.                     }
  532.  
  533.                    if (asize)                   /* Else, use abbrev?    */
  534.                     { if (!Partials)
  535.                         FlushStuff();           /* Flush stuff state.   */
  536.                       OutBin(FindBest+64);      /* Use a meta char.     */
  537.                       NodeOut(FindBest);        /* Now update machine   */
  538.                       for (ch=0; ch<FindSize; ch++)
  539.                         { checksum += Peek(ch);
  540.                         }
  541.                       Remove(FindSize);         /* Flush input string.  */
  542.                       NBytes += FindSize;
  543.                       continue;
  544.                     }
  545.             }
  546.  
  547.            if (!Partials && BinN)               /* Compatibility = pain!*/
  548.                 { register i;
  549.                   for (i=0; i<BinN; i++) OutAscii(BinBuf[i]);
  550.                   BinN = 0;
  551.                 }
  552.  
  553.            ch = Peek(0);
  554.            Remove(1);
  555.            if (ch == -1) break;
  556.            StuffOut(ch);
  557.            NodeOut(MKATOM(ch));
  558.            checksum += ch;
  559.            ++NBytes;
  560.          }
  561.  
  562.         AscFin();
  563.  
  564.         /* Then back to patch up header.                                */
  565.         fseek(out, 0L, 0);              /* rewind.                      */
  566.         WrHeader();
  567.         fclose(out);
  568.         fclose(in);
  569.         return 0;
  570.  }
  571.  
  572. /* Read header of .BSQ input file.
  573.  * If file name in *to has not been set, it is formatted from the
  574.  *   name specified in the header (stripping off directories).
  575.  */
  576.  
  577. unsigned        icheck;                 /* Input checksum from header   */
  578. unsigned        iversion;               /* Input version number from hdr*/
  579. unsigned        ipartn;                 /* Part number                  */
  580. unsigned        inparts;                /* Total number of parts        */
  581.  
  582. RdHeader()
  583.  {      register i, j;
  584.         char line[80];
  585.  
  586.         /* Try to read a new header:                                    */
  587.         fgets (line, 80, in);
  588.         i = sscanf(line, "=== BSQ ver %d %ld bytes %d (%d %d) %s\n",
  589.                 &iversion, &Length, &icheck, &ipartn, &inparts, fname);
  590.  
  591.         if (i != 6)
  592.          { /* Try for an old header:                                    */
  593.            i = sscanf(line, "=== BSQ %d FILE %ld %d %s\n",
  594.                 &iversion, &Length, &icheck, fname);
  595.            if (i != 4) Error("Non-BSQ header format on file %s", from);
  596.          }
  597.  
  598.         if (iversion > VERSION)
  599.                 Error("This is BSQ version %d, file used newer version %d!",
  600.                                 VERSION, iversion);
  601.  
  602.         for (i=0; fname[i]; i++) if (fname[i] < ' ') fname[i] = 0;
  603.         if (!*to)                       /* Use this as output file?     */
  604.            strcpy(to, BaseName(fname));
  605.  
  606.         /* Version-specific features:                                   */
  607.         switch (iversion)
  608.          { case 1:      Partials = 0; CheckColumns = 0; break;
  609.          }
  610.  }
  611.  
  612. /* Write a header to output file:                                       */
  613. WrHeader()
  614.  {
  615.         if (OldFlag)                    /* Old version header?          */
  616.           fprintf(out, "=== BSQ %d FILE %6ld %6u %s",
  617.                 1, NBytes, 0x7FFF & checksum, BaseName(from));
  618.         else
  619.           fprintf(out, "=== BSQ ver %3d %6ld bytes %6u (%2u %2u) %s",
  620.                 VERSION, NBytes, 0x7FFF & checksum, ipartn, inparts,
  621.                                 BaseName(from));
  622.  }
  623.  
  624.  
  625. #define LINSIZ  200                     /* Maximum line size.           */
  626. byte    InBuf[LINSIZ];                  /* Input line buffer            */
  627. int     InPtr=0, InSize=0;              /* Number of chars in InBuf     */
  628. int     Suspect=0, LineNo = 1;          /* Number of suspicious line.   */
  629.  
  630.  
  631. GetC()                                  /* Fetch an input character...  */
  632.  {      while (InPtr == InSize)         /* At end of buffer?            */
  633.                 if (!GetLine()) return EOF;     /* On end-of-file.      */
  634.         return InBuf[InPtr++];
  635.  }
  636.  
  637. GetLine()                               /* Fetch an input line.         */
  638.  {      register i, ch;                 /* Returns zero iff EOF.        */
  639.         InSize = InPtr = 0;
  640.         while (InSize == 0)
  641.          { for (; InSize<LINSIZ; ) switch (ch = getc(in))
  642.                 { case EOF:     return 0;
  643.                   case '\n':    LineNo++;
  644.                   default:      if (ch > ' ')
  645.                                  { InBuf[InSize++] = ch; continue; }
  646.                                 if (!InSize) continue;
  647.                                 goto GotLine;
  648.                 }
  649.          }
  650.  
  651. GotLine:   if (Suspect)
  652.                 Msg("Suspicious text in file %s, line %d\n", from, Suspect);
  653.            if (CheckColumns && (InSize != CheckColumns))
  654.                         Suspect = LineNo;
  655.            else Suspect = 0;
  656.         return InSize;
  657.  }
  658.  
  659. UnSqueeze()
  660.  {      register ch;
  661.         BinInit();
  662.  
  663.         for (;;)
  664.          { ch = GetC();
  665.            if (ch == EOF) break;
  666.            if (ch > ' ') BinOut(ch);
  667.          }
  668.  
  669.         BinFin();
  670.         fclose(in);
  671.         fclose(out);
  672.  
  673.         if (Length != NBytes) Error("File size: %s is %ld, %s was %ld",
  674.                                         to, NBytes, fname, Length);
  675.         if ((icheck & 0x7FFF) != (checksum & 0x7FFF))
  676.                 Error("Checksum error... %x %x\n", icheck,  checksum);
  677.  }
  678.  
  679. /************************************************************************
  680.  *                                                                      *
  681.  * ASCII -> BINARY conversion routines.                                 *
  682.  *   AscInit() - prepare for output.                                    *
  683.  *   StuffOut(byte) - Bit-stuff a byte of 8 bits.                       *
  684.  *   AscFin() - flush buffers                                           *
  685.  *                                                                      *
  686.  ************************************************************************/
  687.  
  688. unsigned outbuf;                /* Partial output bytes.                */
  689. unsigned bits;                  /* number of bits in outbuf             */
  690. unsigned outcol;                /* output chars on current text line    */
  691. unsigned runch, run;            /* For run-length encoding.             */
  692.  
  693. AscInit()
  694.  {      checksum = outcol = outbuf = bits = 0;
  695.         runch = run = 0;
  696.  }
  697.  
  698.  
  699. /* Bit-stuff an 8-bit byte:                                             */
  700. StuffOut(b)
  701.  unsigned b;
  702.  {      register ch;
  703.  
  704.         outbuf <<= 8;           /* Stuff in the new byte.               */
  705.         outbuf |= (b & ((1 << 8)-1));
  706.         bits += 8;              /* 8 more bits.                         */
  707.  
  708.         /* Now add to output, ASCBITS bits/output char:                 */
  709.         while (bits >= ASCBITS)
  710.          { ch = (outbuf >> (bits-ASCBITS)) & 0x3F;      /* 6 Bits.      */
  711.            bits -= ASCBITS;
  712.            OutAscii(ch);
  713.            if (BinN)
  714.                 { register i;
  715.                   for (i=0; i<BinN; i++) OutAscii(BinBuf[i]);
  716.                   BinN = 0;
  717.                 }
  718.          }
  719.  }
  720.  
  721. /* Flush the bit-stuffed output:                                        */
  722. FlushStuff()
  723.  {      if (bits > 0)           /* Output any remaining bits.           */
  724.                 OutAscii(0x3F & (outbuf<<(ASCBITS-bits)));
  725.         outbuf = bits = 0;
  726.         if (BinN)
  727.                 { register i;
  728.                   for (i=0; i<BinN; i++) OutAscii(BinBuf[i]);
  729.                   BinN = 0;
  730.                 }
  731.  }
  732.  
  733. /* Output a number, relocated to printable ASCII range                  */
  734. OutAscii(b)
  735.  {      b += ASCBAS;
  736.         putc(b, out);
  737.         if (++outcol >= COLUMNS) crlf();
  738.  }
  739.  
  740. AscFin()
  741.  {      FlushStuff();
  742.         if (outcol > 0) crlf();
  743.  }
  744.  
  745.  
  746. /* Output a CR/LF:                                                      */
  747. crlf()
  748.  {      /* putc('\r', out); */        putc('\n', out);
  749.         outcol = 0;
  750.  }
  751.  
  752. /************************************************************************
  753.  *                                                                      *
  754.  * BINARY -> ASCII conversion routines.                                 *
  755.  *   BinInit() - prepare for output.                                    *
  756.  *   BinOut(byte) - output a byte of s bits.                            *
  757.  *   BinFin() - flush buffers & close.                                  *
  758.  *                                                                      *
  759.  ************************************************************************/
  760.  
  761. BinInit()
  762.  {      checksum = outcol = outbuf = bits = 0;
  763.  }
  764.  
  765.  
  766. /* Convert another ASCII input character to binary...                   */
  767.  
  768. BinOut(b)
  769.  unsigned b;
  770.  {      register i, ch;
  771.  
  772.         b &= 0177;
  773.         if (b <= ' ') return;           /* Ignore control chars.        */
  774.  
  775.         ch = (b - 041) & ((1 << ASCBITS) -1);   /* Extract ASCBITS      */
  776.  
  777.         if (b >= METABAS)
  778.          { if (!Partials) bits = 0;     /* Flush bit-stuff pipe.        */
  779.            if (b == METARPT)            /* Repeat character?            */
  780.                 { if ((ch=GetC()) == EOF) return;
  781.                   ch = 0x3F & (ch - 041);/* Repeat count.               */
  782.                   while (ch--) BinExp(Previous);
  783.                   return;
  784.                 }
  785.            BinExp(b-METABAS);           /* Expand the output.           */
  786.            NodeOut(b-METABAS);          /* Run the state machine.       */
  787.          }
  788.         else
  789.          { BinOut1(ch);                 /* Bit-stuff input.             */
  790.          }
  791.  }
  792.  
  793.  
  794. BinOut1(b)
  795.  unsigned b;
  796.  {      register ch;
  797.  
  798.         outbuf <<= ASCBITS;             /* Stuff in the new byte.       */
  799.         outbuf |= b;
  800.         bits += ASCBITS;
  801.  
  802.         /* Now add to output, 8 bits/output char:                       */
  803.         while (bits >= 8)
  804.          { ch = ((outbuf >> (bits-8)) & 0xFF);
  805.            NodeOut(MKATOM(ch));         /* Recognise it as output       */
  806.            bits -= 8;
  807.            putc(ch, out);
  808.            ++NBytes;
  809.            checksum += ch;
  810.          }
  811.  }
  812.  
  813. /* Expand & output binary bytes for a node.                             */
  814. BinExp(n)
  815.  NodeID n;
  816.  {      register j;
  817.  
  818.         if (n == UNUSED) return 0;
  819.         if (ATOMIC(n))
  820.          { j = DATA(n);
  821.            putc(j, out);
  822.            ++NBytes;
  823.            checksum += j;
  824.          }
  825.         else
  826.          { BinExp(Nodes[n].Left);
  827.            BinExp(Nodes[n].Right);
  828.          }
  829.  }
  830.  
  831.  
  832. BinFin()
  833.  {      if ((bits > 0) && (NBytes != Length))   /* Output any remaining bits.*/
  834.          { outbuf &= ((1 << bits)-1);
  835.            putc(outbuf, out);
  836.            checksum += outbuf;
  837.            NBytes++;
  838.          }
  839.  }
  840.  
  841. /************************************************************************
  842.  * Misc. utilitiy functions                                             *
  843.  ************************************************************************/
  844.  
  845. Error(a0,a1,a2,a3,a4,a5)                /* Fatal error handler --       */
  846.  {      fprintf(stderr,                 /* Called like printf.          */
  847.                 a0,a1,a2,a3,a4,a5);
  848.         fprintf(stderr, "\n");
  849.         exit(-1);
  850.  }
  851.  
  852. Msg(a0,a1,a2,a3,a4,a5)                  /* Message, for debugging.      */
  853.  {      fprintf(stderr,                 /* Called like printf.          */
  854.                 a0,a1,a2,a3,a4,a5);
  855.         fprintf(stderr, "\n");
  856.  }
  857.