(_dl_start_final): If not USE___THREAD, don't assert
[kopensolaris-gnu/glibc.git] / crypt / README.ufc-crypt
1 The following is the README for UFC-crypt, with those portions deleted
2 that are known to be incorrect for the implementation used with the
3 GNU C library.
4
5
6         UFC-crypt: ultra fast 'crypt' implementation
7         ============================================
8
9         @(#)README      2.27 11 Sep 1996
10
11 Design goals/non goals:
12 ----------------------
13
14 - Crypt implementation plugin compatible with crypt(3)/fcrypt.
15
16 - High performance when used for password cracking.
17
18 - Portable to most 32/64 bit machines.
19
20 - Startup time/mixed salt performance not critical.
21
22 Features of the implementation:
23 ------------------------------
24
25 - On most machines, UFC-crypt runs 30-60 times faster than crypt(3) when
26   invoked repeated times with the same salt and varying passwords.
27
28 - With mostly constant salts, performance is about two to three times
29   that of the default fcrypt implementation shipped with Alec
30   Muffets 'Crack' password cracker. For instructions on how to
31   plug UFC-crypt into 'Crack', see below.
32
33 - With alternating salts, performance is only about twice
34   that of crypt(3).
35
36 - Requires 165 kb for tables.
37
38 Author & licensing etc
39 ----------------------
40
41 UFC-crypt is created by Michael Glad, email: glad@daimi.aau.dk, and has
42 been donated to the Free Software Foundation, Inc. It is covered by the
43 GNU library license version 2, see the file 'COPYING.LIB'.
44
45 NOTES FOR USERS OUTSIDE THE US:
46 ------------------------------
47
48 The US government limits the export of DES based software/hardware.
49 This software is written in Aarhus, Denmark. It can therefore be retrieved
50 from ftp sites outside the US without breaking US law. Please do not
51 ftp it from american sites.
52
53 Benchmark table:
54 ---------------
55
56 The table shows how many operations per second UFC-crypt can
57 do on various machines.
58
59 |--------------|-------------------------------------------|
60 |Machine       |  SUN*  SUN*   HP*     DecStation   HP     |
61 |              | 3/50   ELC  9000/425e    3100    9000/720 |
62 |--------------|-------------------------------------------|
63 | Crypt(3)/sec |  4.6    30     15         25        57    |
64 | Ufc/sec      |  220   990    780       1015      3500    |
65 |--------------|-------------------------------------------|
66 | Speedup      |   48    30     52         40        60    |
67 |--------------|-------------------------------------------|
68
69 *) Compiled using special assembly language support module.
70
71 It seems as if performance is limited by CPU bus and data cache capacity.
72 This also makes the benchmarks debatable compared to a real test with
73 UFC-crypt wired into Crack. However, the table gives an outline of
74 what can be expected.
75
76 Optimizations:
77 -------------
78
79 Here are the optimizations used relative to an ordinary implementation
80 such as the one said to be used in crypt(3).
81
82 Major optimizations
83 *******************
84
85 - Keep data packed as bits in integer variables -- allows for
86   fast permutations & parallel xor's in CPU hardware.
87
88 - Let adjacent final & initial permutations collapse.
89
90 - Keep working data in 'E expanded' format all the time.
91
92 - Implement DES 'f' function mostly by table lookup
93
94 - Calculate the above function on 12 bit basis rather than 6
95   as would be the most natural.
96
97 - Implement setup routines so that performance is limited by the DES
98   inner loops only.
99
100 - Instead of doing salting in the DES inner loops, modify the above tables
101   each time a new salt is seen. According to the BSD crypt code this is
102   ugly :-)
103
104 Minor (dirty) optimizations
105 ***************************
106
107 - combine iterations of DES inner loop so that DES only loops
108   8 times. This saves a lot of variable swapping.
109
110 - Implement key access by a walking pointer rather than coding
111   as array indexing.
112
113 - As described, the table based f function uses a 3 dimensional array:
114
115         sb ['number of 12 bit segment']['12 bit index']['48 bit half index']
116
117   Code the routine with 4 (one dimensional) vectors.
118
119 - Design the internal data format & uglify the DES loops so that
120   the compiler does not need to do bit shifts when indexing vectors.
121
122 Revision history
123 ****************
124
125 UFC patchlevel 0: base version; released to alt.sources on Sep 24 1991
126 UFC patchlevel 1: patch released to alt.sources on Sep 27 1991.
127                   No longer rebuilds sb tables when seeing a new salt.
128 UFC-crypt pl0:    Essentially UFC pl 1. Released to comp.sources.misc
129                   on Oct 22 1991.
130 UFC-crypt pl1:    Released to comp.sources.misc in march 1992
131                   * setkey/encrypt routines added
132                   * added validation/benchmarking programs
133                   * reworked keyschedule setup code
134                   * memory demands reduced
135                   * 64 bit support added