home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / COMPRESS / RLE8_SC.ZIP / RLE8.DOC < prev    next >
Encoding:
Text File  |  1991-07-14  |  2.9 KB  |  94 lines
  1.  
  2.  
  3. Run Length Encoding compressor program 8 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, if you patch the
  18.  
  19. filename stuff, which is ms-dos specific.
  20.  
  21.  
  22.  
  23.  
  24.  
  25. What is run length encoding?
  26.  
  27.  
  28.  
  29. Run Length Encoding, also known as RLE, is a method of compressing data
  30.  
  31. that has a lot of "runs" of bytes (or bits) in it.  A "run" is a series
  32.  
  33. of bytes that are all the same. For instance, the string "THIS IS A
  34.  
  35. VEEEEEEEEEEEEEEEEEEEEEEEERY INTERESTING SENTENCE" has a run of 23 'E's
  36.  
  37. in it.  This could be compressed in the following manner:
  38.  
  39.  
  40.  
  41. THIS IS A V23ERY INTERESTING SENTENCE
  42.  
  43.  
  44.  
  45. resulting in a savings of 20 characters.  A further savings of one
  46.  
  47. character can be realized if the sequence "23" is replaced by a single
  48.  
  49. byte with the value 23.
  50.  
  51.  
  52.  
  53. However, if the text to be encoded is arbitrary, then it may contain
  54.  
  55. numbers as well as letters, and bytes of all possible values.  For this
  56.  
  57. reason, there must be some way to let the decoder know when a compressed
  58.  
  59. run is encountered, and when a sequence to be passed straight through is
  60.  
  61. encountered.  For this reason, the following file format was used:
  62.  
  63.  
  64.  
  65.  
  66.  
  67. ========= tech info =========
  68.  
  69.  
  70.  
  71. 8 bit header version.
  72.  
  73.  
  74.  
  75. File format:
  76.  
  77.  
  78.  
  79. 13 byte original filename, followed by
  80.  
  81.  
  82.  
  83. [ 8 bit header + data ][ 8 bit header + data ][ 8 bit header + data ]
  84.  
  85. etc..
  86.  
  87.  
  88.  
  89. header:
  90.  
  91.  
  92.  
  93.   bit 7         : 1 if following byte is a run
  94.  
  95.   bit 6 - 0     : legnth of run (max 127, min 3)
  96.  
  97.  
  98.  
  99. data: 1 byte : which character run consists of
  100.  
  101.  
  102.  
  103. *** OR ***
  104.  
  105.  
  106.  
  107. header:
  108.  
  109.  
  110.  
  111.   bit 7         : 0 if following bytes are sequence
  112.  
  113.   bit 6 - 0     : legnth of sequence (max 127)
  114.  
  115.  
  116.  
  117. data:  (header AND 0x7F) bytes of data
  118.  
  119.                 : data bytes copied to output stream unchanged
  120.  
  121.  
  122.  
  123. ===============================
  124.  
  125.  
  126.  
  127. bugs:
  128.  
  129.  
  130.  
  131.         None known
  132.  
  133.  
  134.  
  135.  
  136.  
  137. Nasty features :
  138.  
  139.  
  140.  
  141.         1)  When encoder reaches max run length, it is written
  142.  
  143.             out correctly, but is followed by a 1 length run of
  144.  
  145.             the next byte.  Odd.  Reason unknown.
  146.  
  147.  
  148.  
  149.         2)  Better compression could be achieved by having min
  150.  
  151.             compression length and sequence length understood
  152.  
  153.             to be 2.  This would allow an "understood" multiplication
  154.  
  155.             of the seq_len or run_len by 2, since 1 is never used,
  156.  
  157.             allowing sequences of 254 bytes.  This is not likely
  158.  
  159.             to give much better compression in most cases,
  160.  
  161.             and is left as an exercise for the reader.
  162.  
  163.  
  164.  
  165.             Implementing this requires fixing 1 above, too.
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175. Author:  atman%ecst.csuchico.edu@RELAY.CS.NET (internet)
  176.  
  177.          1@9651                               (WWIVnet)
  178.  
  179.          atman of 1:119/666.0                 (fidonet)
  180.  
  181.  
  182.  
  183.  
  184.  
  185. Tell me hi if you use this program!
  186.  
  187.