home *** CD-ROM | disk | FTP | other *** search
/ ftp.barnyard.co.uk / 2015.02.ftp.barnyard.co.uk.tar / ftp.barnyard.co.uk / cpm / walnut-creek-CDROM / CPM / TURBOPAS / SQZTURBO.LBR / TURBOSQZ.DQC / TURBOSQZ.DOC
Text File  |  2000-06-30  |  12KB  |  274 lines
  1. Turbo Pascal File Squeezer / UnSqueezer for CP/M and MsDos/PcDos
  2.  
  3.  
  4. Version 2.0        04/17/85  Bob Berry
  5. -----------
  6.  
  7.     I  originally downloaded these programs from the CompuServe  Borland  SIG.
  8. They were (rather brazenly, I thought) identified as being "CP/M  compatible".
  9. There were, however, the following problems with CP/M compatibility:
  10.  
  11.  
  12.      - Wouldn't  compile.  First   the   text   was   too  large  to  allow
  13.        compilation  in  64k:  Compile time error 99  -  Compiler  Overflow.
  14.        Easily overcome by setting up $Include files.
  15.  
  16.      - Syntax error. The original version included "LongFileSize", which is
  17.        strictly an MsDos turbo function. Replaced with FileSize for CP/M.
  18.  
  19.      - The  input and output files were "File of Char;", which  works  fine
  20.        with Dos. Since the MsDos directory identifies the size of a file in
  21.        bytes, Dos Turbo does not need to do anything special to keep  track
  22.        of  record  count, etc. In CP/M, turbo writes two  integers  at  the
  23.        beginning  of  each "typed" file ("File of ...;")  to  identify  the
  24.        logical  record length and record count. So using "File of Char"  on
  25.        input  leads  turbo to expect the first four bytes of  the  file  to
  26.        contain  the two integers. Naturally this will not be  true  (unless
  27.        the  file  was  actually created BY A TURBO PROGRAM as  a  "File  of
  28.        ..."). For CP/M, the input and output files must be "untyped"  files
  29.        ("File;"), read and written with BlockRead and BlockWrite.
  30.  
  31.      - Recursive  procedures  and  functions   require  the  "A-"  compiler
  32.        directive to work under CP/M turbo.
  33.  
  34.     With  these compatibility problems fixed, one other program bug  appeared.
  35. At end-of-file, the original program immediately sent the SpEof character  and
  36. terminated.  Any  characters  which  were repeated at end  of  file  would  be
  37. truncated.  A CP/M file which ended with a string of fifty ^Z's (ASCII  end-of
  38. file) would be unsqueezed to a single ^Z. A Dos file which ended with a string
  39. of  eighty *'s would unsqueeze to a single *. (Dos files don't need a  ^Z  for
  40. EOF,  as  the  directory  keeps track of the length of  the  file  in  bytes.)
  41. Actually  the  Dos  error would be more obvious than the CP/M  error,  as  the
  42. "physical" CP/M file is almost always larger than the "logical" file (the tail
  43. end of the last sector is normally "garbage".)
  44.  
  45.     The  original  programs  stored (upon squeezing) the  file  checksum,  but
  46. (intentionally?)  avoided  comparing  the  output  file  to  the  checksum  on
  47. unsqueezing. The above "end-of-file repeats" problem caused a checksum  error,
  48. which  I first discovered when testing these for "compatibility"  with  public
  49. domain (CP/M) SQ/USQ.
  50.  
  51.     The current version of the program(s) cause no checksum errors (USQZ  does
  52. check!),  and the programs are compatible with SQ/USQ. Also the  "pre-squeeze"
  53. and  "post-unsqueeze"  files match exactly (a minimum requirement!)  This  has
  54. been verified for CP/M with CRC.COM and for DOS with COMP.COM.
  55.  
  56.     The  Huffman  algorithm  is  apparently  developed  differently  from  the
  57. (standard?)  public  domain SQ/USQ programs (the CRC's of the  squeezed  files
  58. don't match.) However, this is of no significance, as a file squeezed with the
  59. public domain program can be unsqueezed with the turbo program, and vice versa
  60. with  no  checksum  errors,  and with the output  file  exactly  matching  the
  61. original.
  62.  
  63.     Finally,  with the programs working correctly, I set about to make them  a
  64. little less cumbersome. The original programs would be loaded and then ask for
  65. the  file name (no provision to pass the file name from the command  line,  as
  66. "A>SQZ SAMPLE.DOC".) The program would then squeeze or unsqueeze the file  and
  67. boot you back to the system. To do another file, you would start from the "A>"
  68. prompt. I added:
  69.  
  70.     - Provision to specify the first file name on the command line.
  71.  
  72.     - Optional specification of a different output drive.
  73.  
  74.     - CP/M Re-Log to prevent BDOS R/O errors on the output drive. (You  can
  75.       swap disks!)
  76.  
  77.     - Verification of the file checksum on unsqueezing.
  78.  
  79.     - Statistics showing filesize and percentages of output to input files.
  80.  
  81.     - Repeat until a "blank" file name is entered (just <cr>).
  82.  
  83.     - Separate (TESTED and WORKING) routines to accommodate the differences
  84.       between CP/M and MsDos.
  85.  
  86.  
  87.  
  88. Version 2.1   01/29/86   Bob Berry
  89. -----------
  90.  
  91.     - Added WildCard file specifications.
  92.  
  93.     - Added Printer Echo.
  94.  
  95.     - Version 2.1 was prompted primarily by the following:
  96.  
  97.       For  years,  CP/M  (you remember CP/M) has  had  public  domain  file
  98.       compression  programs  available.   Commonly   called  "SQUEEZE"  and
  99.       "UNSQUEEZE"  these  programs conformed to  the  following  "squeezed"
  100.       file definition:
  101.  
  102.       Byte 00 - 01: an integer, FF76H, the squeezed file ID,
  103.                       (stored LSB, MSB or 76 in 00, FF in 01)
  104.       Byte 02 - 03: an integer, the file CheckSum, the integer total
  105.                       of all characters in the original file.
  106.       Byte 04 - ??: the original file name with null (00) terminator
  107.                       (since the squeezed file has a "Q" as the
  108.                        second character of the file extension.)
  109.       Followed By:  an integer, the number of nodes in the tree
  110.                       built when the file was squeezed.
  111.       Followed By:  2*Nodes integers: the tree.
  112.       Followed By:  The Squeezed file.
  113.  
  114.       Recently  at  least  one new format of squeezed  file  has  surfaced.
  115.       Apparently  in  an  attempt to preserve the Date  and  Time  of  last
  116.       write  which  MsDos  (PcDos) stores as part  of  a  directory  entry,
  117.       a new format was devised:
  118.  
  119.       Byte 00 - 01: an integer FFFAH, the new squeezed file ID
  120.       Byte 02 - ??: the original file name, null terminated.
  121.       Followed By:  a null terminated ASCII string with the file date.
  122.       Followed By:  a null (perhaps a null terminated string?)
  123.       Followed By:  an ASCII End-of-file character (^Z = 1AH)
  124.       Followed By:  the file CheckSum
  125.       Followed By:  an integer, the MsDos (FCB format) file date.
  126.       Followed By:  an integer, the MsDos (FCB format) file time.
  127.       Followed By:  an integer, the number of nodes.
  128.       Followed By:  2*Nodes integers: the "tree".
  129.       Followed By:  The Squeezed File.
  130.  
  131.       This  program  will   UnSqueeze   files   of   either  format,  doing
  132.       complete  CheckSum  verification,  and  will do  so  on  either  CP/M
  133.       or DOS computers (by selecting the appropriate .INC module).
  134.  
  135.       Don't  be  surprised,  however, if you discover  yet  another  format
  136.       which  this  program  doesn't  recognize.  It  seems  there  are  new
  137.       Squeeze/UnSqueeze   programs   popping   up   all   the   time,  with
  138.       authors  who  may  not be too concerned about  the  compatibility  of
  139.       their programs with the rest of the universe.
  140.  
  141.  
  142.                                               Bob Berry
  143.                                               CompuServe 76555,167
  144.  
  145.  
  146.  
  147.  
  148.  
  149.   The following documentation is included from the "original" programs.
  150. =======================================================================
  151.  
  152.  
  153. From SQZ.PAS:
  154.  
  155.  
  156. { CP/M compatible file squeezer utility.
  157.  
  158.   This translation uses the Huffman algorithm to develop a binary tree
  159.   representing the decoding information for a variable length bit string code
  160.   for each input value.  Each string's length is in inverse proportion to its
  161.   frequency of appearance in the incoming data stream.  The encoding table is
  162.   derived from the decoding table.
  163.  
  164.   The range of valid values into the Huffman algorithm are the values of a byte
  165.   stored in an integer plus the special endfile value chosen to be an adjacent
  166.   value. Overall, 0-SPEOF.
  167.  
  168.   The algorithm develops the single element trees into a single binary tree by
  169.   forming subtrees rooted in interior nodes having weights equal to the sum of
  170.   weights of all their descendents and having depth counts indicating the
  171.   depth of their longest paths.
  172.  
  173.   When all trees have been formed into a single tree satisfying the heap
  174.   property (on weight, with depth as a tie breaker) then the binary code
  175.   assigned to a leaf (value to be encoded) is then the series of left (0) and
  176.   right (1) paths leading from the root to the leaf.  Note that trees are
  177.   removed from the heaped list by moving the last element over the top element
  178.   and reheaping the shorter list.
  179.  
  180.   To further compress the output code stream, all bytes pass directly through
  181.   except for:
  182.      1) DLE is encoded as (DLE, zero).
  183.      2) repeated byte values (count >= 3) are encoded as (value, DLE, count).
  184.  
  185.   In the original design it was believed that a Huffman code would fit in the
  186.   same number of bits that will hold the sum of all the counts. That was
  187.   disproven by a user's file and was a rare but infamous bug. This version
  188.   attempts to choose among equally weighted subtrees according to their maximum
  189.   depths to avoid unnecessarily long codes. In case that is not sufficient to
  190.   guarantee codes <= 16 bits long, we initially scale the counts so the total
  191.   fits in an unsigned integer, but if codes longer than 16 bits are generated
  192.   the counts are rescaled to a lower ceiling and code generation is retried.
  193.  
  194.   The "node" array of structures contains the nodes of the binary tree. The
  195.   first NUMVALS nodes are the leaves of the tree and represent the values of
  196.   the data bytes being encoded and the special endfile, SPEOF. The remaining
  197.   nodes become the internal nodes of the tree.
  198.  
  199.   Program states:
  200.      NoHist    don't consider previous input
  201.      SentChar  lastchar set, no lookahead yet
  202.      SendNewC  newchar set, previous sequence done
  203.      SendCnt   newchar set, DLE sent, send count next
  204. }
  205.  
  206. (* NOTE: UnReferenced (debug) procedures and functions have been moved here
  207. from SQZ.PAS.
  208.                                                                    Bob Berry *)
  209.  
  210. (*
  211. Procedure PrintBits(len, number: integer);
  212.   var i, j: integer;
  213.   begin
  214.     Write('  code ');
  215.     For i:=len-1 DownTo 0 do
  216.       begin j:=(number shr i) and $0001; write(j:1); end;
  217.     writeln;
  218.   end;
  219. *)
  220.  
  221. (*    Local to InitializeHuffman
  222.     Procedure PrintFrequency;
  223.       Var i, j: integer;
  224.       begin
  225.         j := 0;
  226.         For i:=0 to pred(NumVals do
  227.           If Node[i].Weight>0 then
  228.             begin
  229.               j:=succ(j);
  230.               Writeln(Lst,'Node ',i:3,' Weight is ',Node[i].Weight:4:0);
  231.             end;
  232.         WriteLn(Lst); WriteLn(Lst,'Total Node count is ',j);
  233.       end;
  234.  
  235.     Procedure PrintList;
  236.       Var i:   integer;
  237.           str: string[10];
  238.       begin
  239.         WriteLn(', waiting');   ReadLn(str);
  240.         For i:=0 to pred(NumVals) do
  241.           begin
  242.             Write('Number ',i:3,'  length ',CodeLen[i]:2,
  243.                   '  weight ',node[i].Weight:4:0);
  244.             If CodeLen[i]>0 then PrintBits(CodeLen[i],Code[i])
  245.             else WriteLn;
  246.           end;
  247.       end;
  248.   *)
  249.  
  250. FROM USQZ.PAS:
  251.  
  252. {
  253.   This program unsqueezes a file which has been squeezed or compressed to
  254.   reduce the space required to store it on disk. The program was converted
  255.   from the original version written for CP/M in the C language.  This program
  256.   can be used to unsqueeze files which have been downloaded from RCP/M systems
  257.   where almost all files are saved in this squeezed format.
  258.  
  259.   The technique used is the Huffman encoding technique which converts the most
  260.   common characters in the input file to a compressed bit stream of data. This
  261.   program unsqueezes such a Huffman encoded file.
  262.  
  263.   PUBLIC DOMAIN - Feel free to distribute this program. Do not distribute it by
  264.   commercial means or make any charge for this pgm.
  265.  
  266.   Version 1.0  - 09/05/82  Scott Loftesness
  267.   Version 1.1  - 01/06/83  Added capability to strip off parity bit if
  268.                            output file is text. Ernie LeMay 71435,730
  269.   Version 1.2  - 07/20/84  converted to Turbo Pascal. Steve Freeman
  270. }
  271.  
  272.  
  273.  
  274.