android/kernel/goldfish.git/refs/heads/android-goldfish-2.6.29

Below is the original README file from the descore.shar package. ------------------------------------------------------------------------------ des - fast & portable DES encryption & decryption. Copyright (C) 1992 Dana L. How This program is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. Author's address: how@isl.stanford.edu $Id: README,v 1.15 1992/05/20 00:25:32 how E $ ==>> To compile after untarring/unsharring, just `make' <<== This package was designed with the following goals: 1. Highest possible encryption/decryption PERFORMANCE. 2. PORTABILITY to any byte-addressable host with a 32bit unsigned C type 3. Plug-compatible replacement for KERBEROS's low-level routines. This second release includes a number of performance enhancements for register-starved machines. My discussions with Richard Outerbridge, 71755.204@compuserve.com, sparked a number of these enhancements. To more rapidly understand the code in this package, inspect desSmallFips.i (created by typing `make') BEFORE you tackle desCode.h. The latter is set up in a parameterized fashion so it can easily be modified by speed-daemon hackers in pursuit of that last microsecond. You will find it more illuminating to inspect one specific implementation, and then move on to the common abstract skeleton with this one in mind. performance comparison to other available des code which i could compile on a SPARCStation 1 (cc -O4, gcc -O2): this code (byte-order independent): 30us per encryption (options: 64k tables, no IP/FP) 33us per encryption (options: 64k tables, FIPS standard bit ordering) 45us per encryption (options: 2k tables, no IP/FP) 48us per encryption (options: 2k tables, FIPS standard bit ordering) 275us to set a new key (uses 1k of key tables) this has the quickest encryption/decryption routines i've seen. since i was interested in fast des filters rather than crypt(3) and password cracking, i haven't really bothered yet to speed up the key setting routine. also, i have no interest in re-implementing all the other junk in the mit kerberos des library, so i've just provided my routines with little stub interfaces so they can be used as drop-in replacements with mit's code or any of the mit- compatible packages below. (note that the first two timings above are highly variable because of cache effects). kerberos des replacement from australia (version 1.95): 53us per encryption (uses 2k of tables) 96us to set a new key (uses 2.25k of key tables) so despite the author's inclusion of some of the performance improvements i had suggested to him, this package's encryption/decryption is still slower on the sparc and 68000. more specifically, 19-40% slower on the 68020 and 11-35% slower on the sparc, depending on the compiler; in full gory detail (ALT_ECB is a libdes variant): compiler machine desCore libdes ALT_ECB slower by gcc 2.1 -O2 Sun 3/110 304 uS 369.5uS 461.8uS 22% cc -O1 Sun 3/110 336 uS 436.6uS 399.3uS 19% cc -O2 Sun 3/110 360 uS 532.4uS 505.1uS 40% cc -O4 Sun 3/110 365 uS 532.3uS 505.3uS 38% gcc 2.1 -O2 Sun 4/50 48 uS 53.4uS 57.5uS 11% cc -O2 Sun 4/50 48 uS 64.6uS 64.7uS 35% cc -O4 Sun 4/50 48 uS 64.7uS 64.9uS 35% (my time measurements are not as accurate as his). the comments in my first release of desCore on version 1.92: 68us per encryption (uses 2k of tables) 96us to set a new key (uses 2.25k of key tables) this is a very nice package which implements the most important of the optimizations which i did in my encryption routines. it's a bit weak on common low-level optimizations which is why it's 39%-106% slower. because he was interested in fast crypt(3) and password-cracking applications, he also used the same ideas to speed up the key-setting routines with impressive results. (at some point i may do the same in my package). he also implements the rest of the mit des library. (code from eay@psych.psy.uq.oz.au via comp.sources.misc) fast crypt(3) package from denmark: the des routine here is buried inside a loop to do the crypt function and i didn't feel like ripping it out and measuring performance. his code takes 26 sparc instructions to compute one des iteration; above, Quick (64k) takes 21 and Small (2k) takes 37. he claims to use 280k of tables but the iteration calculation seems to use only 128k. his tables and code are machine independent. (code from glad@daimi.aau.dk via alt.sources or comp.sources.misc) swedish reimplementation of Kerberos des library 108us per encryption (uses 34k worth of tables) 134us to set a new key (uses 32k of key tables to get this speed!) the tables used seem to be machine-independent; he seems to have included a lot of special case code so that, e.g., `long' loads can be used instead of 4 `char' loads when the machine's architecture allows it. (code obtained from chalmers.se:pub/des) crack 3.3c package from england: as in crypt above, the des routine is buried in a loop. it's also very modified for crypt. his iteration code uses 16k of tables and appears to be slow. (code obtained from aem@aber.ac.uk via alt.sources or comp.sources.misc) ``highly optimized'' and tweaked Kerberos/Athena code (byte-order dependent): 165us per encryption (uses 6k worth of tables) 478us to set a new key (uses <1k of key tables) so despite the comments in this code, it was possible to get faster code AND smaller tables, as well as making the tables machine-independent. (code obtained from prep.ai.mit.edu) UC Berkeley code (depends on machine-endedness): 226us per encryption 10848us to set a new key table sizes are unclear, but they don't look very small (code obtained from wuarchive.wustl.edu) motivation and history a while ago i wanted some des routines and the routines documented on sun's man pages either didn't exist or dumped core. i had heard of kerberos, and knew that it used des, so i figured i'd use its routines. but once i got it and looked at the code, it really set off a lot of pet peeves - it was too convoluted, the code had been written without taking advantage of the regular structure of operations such as IP, E, and FP (i.e. the author didn't sit down and think before coding), it was excessively slow, the author had attempted to clarify the code by adding MORE statements to make the data movement more `consistent' instead of simplifying his implementation and cutting down on all data movement (in particular, his use of L1, R1, L2, R2), and it was full of idiotic `tweaks' for particular machines which failed to deliver significant speedups but which did obfuscate everything. so i took the test data from his verification program and rewrote everything else. a while later i ran across the great crypt(3) package mentioned above. the fact that this guy was computing 2 sboxes per table lookup rather than one (and using a MUCH larger table in the process) emboldened me to do the same - it was a trivial change from which i had been scared away by the larger table size. in his case he didn't realize you don't need to keep the working data in TWO forms, one for easy use of half the sboxes in indexing, the other for easy use of the other half; instead you can keep it in the form for the first half and use a simple rotate to get the other half. this means i have (al