home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / COMPRESS / RLE16_SC.ZIP / RLE16.DOC < prev    next >
Encoding:
Text File  |  1991-07-14  |  4.6 KB  |  119 lines
  1.  
  2.  
  3. Run Length Encoding compressor program 16 bit header version
  4.  
  5.  
  6.  
  7. Written by Shaun Case 1991 in Borland C++ 2.0
  8.  
  9.                               with sizeof (int) == 2
  10.  
  11.  
  12.  
  13. This program and its source code are Public Domain.
  14.  
  15. This program should be portable to any machine with
  16.  
  17. 2 byte short ints and 8 bit bytes.
  18.  
  19.  
  20.  
  21.  
  22.  
  23. What is run length encoding?
  24.  
  25.  
  26.  
  27. Run Length Encoding, also known as RLE, is a method of compressing data
  28.  
  29. that has a lot of "runs" of bytes (or bits) in it.  A "run" is a series
  30.  
  31. of bytes that are all the same. For instance, the string "THIS IS A
  32.  
  33. VEEEEEEEEEEEEEEEEEEEEEEEERY INTERESTING SENTENCE" has a run of 23 'E's
  34.  
  35. in it.  This could be compressed in the following manner:
  36.  
  37.  
  38.  
  39. THIS IS A V23ERY INTERESTING SENTENCE
  40.  
  41.  
  42.  
  43. resulting in a savings of 20 characters.  A further savings of one
  44.  
  45. character can be realized if the sequence "23" is replaced by a single
  46.  
  47. byte with the value 23.
  48.  
  49.  
  50.  
  51. However, if the text to be encoded is arbitrary, then it may contain
  52.  
  53. numbers as well as letters, and bytes of all possible values.  For this
  54.  
  55. reason, there must be some way to let the decoder know when a compressed
  56.  
  57. run is encountered, and when a sequence to be passed straight through is
  58.  
  59. encountered.  For this reason, the following file format was used:
  60.  
  61.  
  62.  
  63.  
  64.  
  65. ========= tech info =========
  66.  
  67.  
  68.  
  69. 16 bit header version.
  70.  
  71.  
  72.  
  73. File format:
  74.  
  75.  
  76.  
  77. 13 bytes : original filename, followed by:
  78.  
  79.  
  80.  
  81. [ 16 bit header + data ][ 16 bit header + data ][16 bit header + data ]
  82.  
  83. etc..
  84.  
  85.  
  86.  
  87. header:
  88.  
  89. [lo byte][hi byte] ==> turn into 16 bit int ==>
  90.  
  91.  
  92.  
  93.   bit 15        : 1 if following byte is a run
  94.  
  95.   bit 14 - 0    : length of run (max 32767, min 4)
  96.  
  97.  
  98.  
  99. data: 1 byte : which character run consists of
  100.  
  101.  
  102.  
  103. *** OR ***
  104.  
  105.  
  106.  
  107. header:
  108.  
  109. [lo byte][hi byte] ==> turn into 16 bit int ==>
  110.  
  111.  
  112.  
  113.   bit 15        : 0 if following bytes are sequence
  114.  
  115.   bit 14 - 0    : length of sequence (max 32767)
  116.  
  117.  
  118.  
  119. data:  (header & 0x7FFF) bytes of data
  120.  
  121.                 : data bytes copied to output stream unchanged
  122.  
  123.  
  124.  
  125. ===============================
  126.  
  127.  
  128.  
  129. bugs:
  130.  
  131.  
  132.  
  133.         None known
  134.  
  135.  
  136.  
  137.  
  138.  
  139. Nasty features :
  140.  
  141.  
  142.  
  143.         1)  In 8 bit version, when encoder reaches max run length, it is
  144.  
  145.             written out correctly, but is followed by a 1 length run of
  146.  
  147.             the next byte.  Odd.  Reason unknown.  This version
  148.  
  149.             probably does it too, but I haven't tested it.
  150.  
  151.  
  152.  
  153.         2)  Better compression could be achieved by having min
  154.  
  155.             compression length and sequence length understood to be 4.
  156.  
  157.             This would allow an "understood" multiplication of the
  158.  
  159.             seq_len or run_len by 4, since 1 is never (should never be)
  160.  
  161.             used, allowing sequences of 131068 bytes.
  162.  
  163.  
  164.  
  165.             Implementing this requires fixing 1 above, too.
  166.  
  167.  
  168.  
  169.         4)  This 16 bit "improvement" is very unlikley to give better
  170.  
  171.             compresssion than the 8 bit version for data consisting of
  172.  
  173.             executable code, English or or other natural language text,
  174.  
  175.             netnews, BBS messages, or just about anything else other
  176.  
  177.             than large simple graphics images or other types of data
  178.  
  179.             that consist almost entirely of very long runs of
  180.  
  181.             characters.  In most cases, this program will actually
  182.  
  183.             INCREASE the size of the data file slightly, due to the
  184.  
  185.             overhead needed for sequences between runs.  It also runs
  186.  
  187.             about 10% slower than the 8 bit version due to the use of
  188.  
  189.             shifts and logical operators.  Mainly it was an experiment
  190.  
  191.             that yielded disappointing results.  However, here it is,
  192.  
  193.             for you to use and abuse.
  194.  
  195.  
  196.  
  197.         5)  Portability -- this program is "pretty portable."  The stuff
  198.  
  199.             dealing with dos filenames should be removed, but that should
  200.  
  201.             be about it, unless you want to make the datafiles portable
  202.  
  203.             too, which is another story.
  204.  
  205.  
  206.  
  207.         6)  There is a lack of error checking when bytes are written out
  208.  
  209.             to the output file.  Bytes are written in lots of places,
  210.  
  211.             and I didn't get around to doing error checking on any of them,
  212.  
  213.             since my application was going to run only in memory, and
  214.  
  215.             all the fputc() calls were going to be changed to pokes or
  216.  
  217.             pointer-directed stuffing.  If you are going to use this program
  218.  
  219.             in a disk based application, you should really put EOF checks
  220.  
  221.             after each fputc().
  222.  
  223.  
  224.  
  225. Author:  atman%ecst.csuchico.edu@RELAY.CS.NET (internet)
  226.  
  227.          1@9651                               (WWIVnet)
  228.  
  229.          atman of 1:119/666.0                 (fidonet)
  230.  
  231.  
  232.  
  233.  
  234.  
  235. Tell me hi if you use this program!
  236.  
  237.