home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 13 / CD_ASCQ_13_0494.iso / news / 2417 / uc2 / backgrnd.doc next >
Text File  |  1993-12-31  |  14KB  |  335 lines
  1. 7. BACKGRND: concepts, program design, compressor design, benchmarks
  2. ====================================================================
  3.  
  4. Although many aspects of UC look simple and straightforward, UC is a
  5. very advanced program.
  6.  
  7. This document contains the following paragraphs:
  8.  
  9.         - A. Inside UC
  10.         - B. Compression technology
  11.         - C. Damage protection technology
  12.         - D. Benchmarking
  13.  
  14. To jump to a certain paragraph, press the corresponding letter. To
  15. jump to a specific document/chapter, press the corresponding digit.
  16. See chapter 1 paragraph E for an overview of all documentation.
  17.  
  18.  
  19. 7.A INSIDE UC.
  20. ==============
  21.  
  22. Here a rough overview of the internals of UC is given. It can give
  23. those who are interested more insight into what is going on INSIDE
  24. UltraCompressor II (tm).
  25.  
  26. If you want more detailed technical information (e.g. for making add-on
  27. tools) you can always contact us. Please note however we do not intend
  28. to supply the source code of UC to third parties. Sample add-on tools
  29. (including their source code) are available on request.
  30.  
  31. UC is programmed in C++ and assembly language (for the time critical
  32. sections). It is devised in a number of modules which are briefly
  33. described in this section.
  34.  
  35.  
  36. Overview
  37. --------
  38.                         GENERAL CONTROL
  39.                            main
  40.                            command interpreter
  41.                            super manager
  42.                            archive I/O
  43.  
  44.  
  45.    SYSTEM SERVICES                             COMPRESSION SERVICES
  46.       video                                       neuro manager
  47.       lowlevel I/O                                ultra engine
  48.       memory manager
  49.       virtual memory manager
  50.                                                RELIABILITY SERVICES
  51.                                                   error handler
  52.    OTHER                                          damage protection
  53.       lister                                      guard
  54.       viewer                                      test
  55.  
  56.  
  57. General control
  58. ---------------
  59.    MAIN
  60.       The main module calls all initialization routines and takes care
  61.       of the configuration and help menus.
  62.  
  63.    COMMAND INTERPRETER
  64.       The command line and script files are interpreted in this
  65.       module.
  66.  
  67.    SUPER MANAGER
  68.       Finds out what should happen (e.g. ask the command interpreter,
  69.       scan the disk and the archive), and makes it happen (call the
  70.       datacompressor etc.). This module is the most complex module of
  71.       UC, but it delegates a lot of hard work to other modules.
  72.  
  73.    ARCHIVE I/O
  74.       Here the archive file format is managed. Conversion between
  75.       external (compressed flat file) and internal (object database)
  76.       formats, as well as all kinds of integrity checks are performed.
  77.  
  78. System services
  79. ---------------
  80.    VIDEO
  81.       The keyboard, screen and output file (in case of redirection)
  82.       are managed here.
  83.  
  84.    LOWLEVEL I/O
  85.       Here lowlevel file specifics and networking are handled. Also
  86.       this module takes care of file caching, an essential issue in
  87.       making UC perform fast on (floppy) disk and network access.
  88.  
  89.    MEMORY MANAGER (MM)
  90.       This module manages base memory, XMS and EMS. The MM decides
  91.       which component of the program can get memory, and how much
  92.       memory it can get, to optimize overall performance.
  93.  
  94.    VIRTUAL MEMORY MANAGER (VMM)
  95.       This module manages the 'persistent object database' containing
  96.       the central directory of an archive and numerous links needed to
  97.       make processing as efficient as possible. No matter the amount
  98.       of data in the VMM, it can always work (fast) with only a small
  99.       amount of memory. VMM uses the memory manager to optimize its
  100.       performance wherever possible. The VMM also supplies pipeline
  101.       services for decoupling translation (archive I/O) and compression
  102.       logic.
  103.  
  104. Compression services
  105. --------------------
  106.    NEURO MANAGER
  107.       This component makes 'neuro models' of collections of files.
  108.       These neuro models allow UC to use similarities between
  109.       different files to compress all files even further. The
  110.       analyzation phase of UC refers to the creation of neuro models
  111.       based on found files. The optimizing phase (which is different
  112.       from the optimize command) refers to the compression of the
  113.       neuro models. One special neuro model (the 'master') is built
  114.       into the compressor. This model is used to improve compression
  115.       of the neuro models. The master contains information about the
  116.       general structure of common file types such as: documents,
  117.       spreadsheets, databases, sources etc..
  118.  
  119.    ULTRA ENGINE
  120.       The bare high speed compressor/decompressor. Based on a neuro
  121.       model the redundancy of a stream of data is analyzed and
  122.       compressed.
  123.  
  124. Reliability services
  125. --------------------
  126.    ERROR HANDLER
  127.       The error handler traps DOS system errors and handles them in a
  128.       neat and consistent way. It often allows the user to go to DOS,
  129.       solve the problem, leave DOS and continue where UC has stopped.
  130.       The error handler makes it impossible for the user to specify
  131.       'ignore', (an unfortunate option DOS offers if something goes
  132.       wrong).
  133.  
  134.    DAMAGE PROTECTION
  135.       This module handles damage protection, damage detection and
  136.       damage recovery.
  137.  
  138.    GUARD
  139.       The guard continuously checks the internal integrity of UC. It
  140.       is often able to prevent damage caused by e.g. software
  141.       conflicts or hardware problems.
  142.  
  143.    TEST (only available in beta versions)
  144.       Tests and interrogates various components of UC during
  145.       execution.
  146.  
  147. Other
  148. -----
  149.    LISTER
  150.       Shows contents of archive in various formats.
  151.  
  152.    VIEWER
  153.       Online help viewer.
  154.  
  155.  
  156. 7.B COMPRESSION TECHNOLOGY.
  157. ===========================
  158.  
  159. UC significantly outperforms existing datacompression technology. For
  160. those interested in background information, we will discuss WHY and
  161. HOW UC is capable of doing this.
  162.  
  163. AIP-NL would like to specifically thank the University of Utrecht, Drs.
  164. Ing. D. Bezemer, Prof. Dr. J. van Leeuwen, Dr. P. van Oostrum and Drs.
  165. Ing. N.E. de Vries for their significant participation in the design
  166. of the UC compression engine. The detailed design is on request
  167. available at the public library of the University of Utrecht.
  168.  
  169. To begin, we will give a brief explanation of AR002. Most modern
  170. datacompressors (ARJ, LHA, ZIP, ZOO) are derivatives of AR002. AR002
  171. was designed by Haruhiko Okumura.
  172.  
  173. AR002, a two phase compressor
  174. -----------------------------
  175.    DATA <-> (#1, LZ) <-> (grouping) <-> (#2, Huffman) <-> COMPRESSED
  176.  
  177.    In phase #1 (the 'LempelZiv' phase) 'matches' are located. Matches
  178.    are strings of data which are equal. The string 'hello there hello'
  179.    can be converted to 'hello there '(-12,5) since 'hello' is matched.
  180.    In general ARJ, LHA, ZIP and ZOO can find matches with a maximum
  181.    distance of about 32700, and a maximum length of about 500 (rough
  182.    estimates).
  183.  
  184.    In phase #2 (the 'Huffman' phase) the output of phase #1 is divided
  185.    into blocks. For each block statistics are analyzed (for example
  186.    the compressor notices the character 'e' is used much more often
  187.    than 'q'). From this analysis an optimal translation table
  188.    ('Huffman tree') is generated (e.g. 'e'=001 'q'=100100010). The
  189.    compressed block then consists of the Huffman tree and the
  190.    translated contents of the block.
  191.  
  192.    The storage of the Huffman tree, at the beginning of each block, is
  193.    a complicated matter which we will not cover here.
  194.  
  195.    The number of different values phase #1 can generate is very large
  196.    (e.g. all 256 possible values of a byte, and about 32700 * 500
  197.    different match discriptions). Since it is very inefficient to make
  198.    a Huffman tree for all those possible values, the values are
  199.    grouped, and statistics are gathered for the groups instead of the
  200.    single values. LHA, ZOO, ARJ and ZIP all use various methods to
  201.    realize this grouping.
  202.  
  203. UltraEngine
  204. -----------
  205.    The UltraEngine is also an AR002 derivative, but with some
  206.    fundamental enhancements. These enhancements can be divided into
  207.    two major features: the core engine and the neuro manager.
  208.  
  209.    The neuro manager is the most significant enhancement. Ordinary
  210.    datacompression engines always start completely 'blank', knowing
  211.    absolutely nothing about the data they are going to compress. The
  212.    neuro-manager collects generic information about a group of files.
  213.    For example a collection of *.DOC files will all have similar
  214.    characteristics, and share common text strings like 'paper'. The
  215.    neuro-manager collects this common 'knowledge' in a neuro model.
  216.    This neuro model is used to make the core engine much smarter when
  217.    similar files are compressed.
  218.  
  219.    UC has a neuro model ('master') built into the executable as well.
  220.    This master contains information about common file formats. It
  221.    contains for example information about spreadsheets, databases,
  222.    wordprocessors, programming languages, common words in: English,
  223.    French, German and Dutch etc.. This built in information improves
  224.    compression.
  225.  
  226.    The core engine also has some enhancements over the basic AR002
  227.    engine.
  228.  
  229.    The match engine has been replaced by a completely new one. This
  230.    new engine is capable of finding matches at a distance of 64000 and
  231.    with a maximum length of 30000.
  232.  
  233.    Also the way in which blocks of data are gathered for further
  234.    Huffman compression is completely different. Instead of looking at
  235.    one block at a time, the core engine attempts to 'learn' from
  236.    previous blocks so less information is needed to encode statistical
  237.    information of a block.
  238.  
  239. Alternative
  240. -----------
  241.    A collection of files can also be compressed more, with the often
  242.    used TAR+COMPRESS 'trick'. First collect all files in a single
  243.    large file, and then compress this single large file at once.
  244.    Especially for large collections of small files, this improves
  245.    compression significantly. This approach can be reached with ARJ as
  246.    well, by first compressing with ARJ -m0, and compressing the
  247.    resulting archive again with ARJ -jm1.
  248.  
  249.    It should be noted, however, that the UltraEngine approach works
  250.    much better. First of all, the compression is better. The neuro
  251.    manager is much smarter than just a simple concatenation. This can
  252.    be verified by compressing the output of ARJ -m0 with UC -tt. Also
  253.    the core engine is fine tuned for optimal performance in
  254.    cooperation with neuro models. The 64000 byte match length is one
  255.    of the essential enhancements.
  256.  
  257.    Another reason why the UC approach is much better, is random access.
  258.    Try to delete a single file of a collection of 5000 C files when
  259.    ARJ -m0/-jm1 has been used, or try to add or extract SOME files. UC
  260.    will mostly do this much faster than ordinary archivers (this is a
  261.    result of better caching and a better file format), and remarkably
  262.    faster than a collect/compress archiver.
  263.  
  264.  
  265. 7.C DAMAGE PROTECTION TECHNOLOGY.
  266. =================================
  267.  
  268. When an archive is 'damage protected' with the P command, it becomes
  269. resistant to a certain amount of damage. This paragraph explains how
  270. UC achieves this.
  271.  
  272. We will start with a mathematical operator called 'XOR'. XOR has the
  273. following properties:
  274.  
  275. 0 XOR 0 = 0; 0 XOR 1 = 1; 1 XOR 0 = 1; 1 XOR 1 = 0
  276.  
  277. if   a1 XOR a2 XOR a3 XOR a4 XOR a5 = xx
  278. then a1 XOR xx XOR a3 XOR a4 XOR a5 = a2
  279. and  a1 XOR a2 XOR a3 XOR xx XOR a5 = a4
  280. etc.
  281.  
  282. This exactly shows the essence of damage protection, a1..a5 are the
  283. bare data, xx is special (damage recovery) information which can be
  284. used to restore bare data if it somehow has been destroyed.
  285.  
  286. In practice UC XOR's groups of 512 bytes (sectors) instead of single
  287. bits. To determine if a specific sector is correct or damaged a
  288. checksum of all sectors is included in the damage recovery
  289. information.
  290.  
  291. About 1% of damage protection information is added to an archive. For
  292. short files this is a single recovery sector (meaning up to 1 damaged
  293. sector can be recovered). But if the archive is longer multiple damage
  294. recovery sectors are added, for example one for odd and one for even
  295. sectors.
  296.  
  297.  
  298. 7.D BENCHMARKING.
  299. =================
  300.  
  301. Benchmarking is a very complicated matter. It is always possible to
  302. create a legitimate looking benchmark which makes product A or product
  303. B look better. A nice example of this can be seen by just looking at
  304. some ads.
  305.  
  306. Some products are even optimized for running benchmarks. An
  307. unfortunate habit which makes it even more difficult to compare
  308. products.
  309.  
  310. We have done a successful attempt to optimize UC for daily 'real life'
  311. use. This means it compresses fast and it decompresses very fast.
  312.  
  313. But when archives are used intensively, the bare compression/
  314. decompression speed is only an aspect of the whole picture. What is
  315. also very important is how efficient updates are performed. Especially
  316. when 'the going gets tough', for example when a large archive resides
  317. on a floppy disk, or when the archive is on a network, UC can be much
  318. faster than other products.
  319.  
  320. An unfortunate problem in benchmarking archivers is the 'Calgary
  321. Compression Corpus', which is often used to compare datacompressors.
  322. Well, UC will do noticeably better than other compressors with this
  323. test, yet the real power of the compression engine is not used in this
  324. unrealistic test. When collections of 'real life' files (e.g. a large
  325. collection of documents, or sources, or the average archive one finds
  326. on a BBS) is compressed the difference between UC and other products
  327. becomes much more significant.
  328.  
  329. Of course, although performance is very important, it is only one
  330. aspect in the usability of a product.
  331.  
  332. In general it is our opinion that you, the user, are the best person
  333. to perform benchmarks. Try the product the way you would actually USE
  334. it and see for yourself.
  335.