lib/replace/crypt.c

   1 /*
   2    This bit of code was derived from the UFC-crypt package which
   3    carries the following copyright
   4
   5    Modified for use by Samba by Andrew Tridgell, October 1994
   6
   7    Note that this routine is only faster on some machines. Under Linux 1.1.51
   8    libc 4.5.26 I actually found this routine to be slightly slower.
   9
  10    Under SunOS I found a huge speedup by using these routines
  11    (a factor of 20 or so)
  12
  13    Warning: I've had a report from Steve Kennedy <steve@gbnet.org>
  14    that this crypt routine may sometimes get the wrong answer. Only
  15    use UFC_CRYT if you really need it.
  16
  17 */
  18
  19 #include "replace.h"
  20
  21 #ifndef HAVE_CRYPT
  22
  23 /*
  24  * UFC-crypt: ultra fast crypt(3) implementation
  25  *
  26  * Copyright (C) 1991-1998, Free Software Foundation, Inc.
  27  *
  28  * This library is free software; you can redistribute it and/or
  29  * modify it under the terms of the GNU Lesser General Public
  30  * License as published by the Free Software Foundation; either
  31  * version 3 of the License, or (at your option) any later version.
  32  *
  33  * This library is distributed in the hope that it will be useful,
  34  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  35  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  36  * Library General Public License for more details.
  37  *
  38  * You should have received a copy of the GNU Lesser General Public
  39  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  40  *
  41  * @(#)crypt_util.c     2.31 02/08/92
  42  *
  43  * Support routines
  44  *
  45  */
  46
  47
  48 #ifndef long32
  49 #define long32 int32_t
  50 #endif
  51
  52 #ifndef long64
  53 #define long64 int64_t
  54 #endif
  55
  56 #ifndef ufc_long
  57 #define ufc_long unsigned
  58 #endif
  59
  60 #ifndef _UFC_64_
  61 #define _UFC_32_
  62 #endif
  63
  64 /*
  65  * Permutation done once on the 56 bit
  66  *  key derived from the original 8 byte ASCII key.
  67  */
  68 static int pc1[56] = {
  69   57, 49, 41, 33, 25, 17,  9,  1, 58, 50, 42, 34, 26, 18,
  70   10,  2, 59, 51, 43, 35, 27, 19, 11,  3, 60, 52, 44, 36,
  71   63, 55, 47, 39, 31, 23, 15,  7, 62, 54, 46, 38, 30, 22,
  72   14,  6, 61, 53, 45, 37, 29, 21, 13,  5, 28, 20, 12,  4
  73 };
  74
  75 /*
  76  * How much to rotate each 28 bit half of the pc1 permutated
  77  *  56 bit key before using pc2 to give the i' key
  78  */
  79 static int rots[16] = {
  80   1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
  81 };
  82
  83 /*
  84  * Permutation giving the key
  85  * of the i' DES round
  86  */
  87 static int pc2[48] = {
  88   14, 17, 11, 24,  1,  5,  3, 28, 15,  6, 21, 10,
  89   23, 19, 12,  4, 26,  8, 16,  7, 27, 20, 13,  2,
  90   41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
  91   44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
  92 };
  93
  94 /*
  95  * The E expansion table which selects
  96  * bits from the 32 bit intermediate result.
  97  */
  98 static int esel[48] = {
  99   32,  1,  2,  3,  4,  5,  4,  5,  6,  7,  8,  9,
 100    8,  9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
 101   16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
 102   24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32,  1
 103 };
 104 static int e_inverse[64];
 105
 106 /*
 107  * Permutation done on the
 108  * result of sbox lookups
 109  */
 110 static int perm32[32] = {
 111   16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
 112   2,   8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
 113 };
 114
 115 /*
 116  * The sboxes
 117  */
 118 static int sbox[8][4][16]= {
 119         { { 14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7 },
 120           {  0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8 },
 121           {  4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0 },
 122           { 15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13 }
 123         },
 124
 125         { { 15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10 },
 126           {  3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5 },
 127           {  0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15 },
 128           { 13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9 }
 129         },
 130
 131         { { 10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8 },
 132           { 13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1 },
 133           { 13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7 },
 134           {  1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12 }
 135         },
 136
 137         { {  7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15 },
 138           { 13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9 },
 139           { 10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4 },
 140           {  3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14 }
 141         },
 142
 143         { {  2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9 },
 144           { 14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6 },
 145           {  4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14 },
 146           { 11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3 }
 147         },
 148
 149         { { 12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11 },
 150           { 10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8 },
 151           {  9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6 },
 152           {  4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13 }
 153         },
 154
 155         { {  4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1 },
 156           { 13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6 },
 157           {  1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2 },
 158           {  6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12 }
 159         },
 160
 161         { { 13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7 },
 162           {  1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2 },
 163           {  7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8 },
 164           {  2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11 }
 165         }
 166 };
 167
 168 /*
 169  * This is the final
 170  * permutation matrix
 171  */
 172 static int final_perm[64] = {
 173   40,  8, 48, 16, 56, 24, 64, 32, 39,  7, 47, 15, 55, 23, 63, 31,
 174   38,  6, 46, 14, 54, 22, 62, 30, 37,  5, 45, 13, 53, 21, 61, 29,
 175   36,  4, 44, 12, 52, 20, 60, 28, 35,  3, 43, 11, 51, 19, 59, 27,
 176   34,  2, 42, 10, 50, 18, 58, 26, 33,  1, 41,  9, 49, 17, 57, 25
 177 };
 178
 179 /*
 180  * The 16 DES keys in BITMASK format
 181  */
 182 #ifdef _UFC_32_
 183 long32 _ufc_keytab[16][2];
 184 #endif
 185
 186 #ifdef _UFC_64_
 187 long64 _ufc_keytab[16];
 188 #endif
 189
 190
 191 #define ascii_to_bin(c) ((c)>='a'?(c-59):(c)>='A'?((c)-53):(c)-'.')
 192 #define bin_to_ascii(c) ((c)>=38?((c)-38+'a'):(c)>=12?((c)-12+'A'):(c)+'.')
 193
 194 /* Macro to set a bit (0..23) */
 195 #define BITMASK(i) ( (1<<(11-(i)%12+3)) << ((i)<12?16:0) )
 196
 197 /*
 198  * sb arrays:
 199  *
 200  * Workhorses of the inner loop of the DES implementation.
 201  * They do sbox lookup, shifting of this  value, 32 bit
 202  * permutation and E permutation for the next round.
 203  *
 204  * Kept in 'BITMASK' format.
 205  */
 206
 207 #ifdef _UFC_32_
 208 long32 _ufc_sb0[8192], _ufc_sb1[8192], _ufc_sb2[8192], _ufc_sb3[8192];
 209 static long32 *sb[4] = {_ufc_sb0, _ufc_sb1, _ufc_sb2, _ufc_sb3};
 210 #endif
 211
 212 #ifdef _UFC_64_
 213 long64 _ufc_sb0[4096], _ufc_sb1[4096], _ufc_sb2[4096], _ufc_sb3[4096];
 214 static long64 *sb[4] = {_ufc_sb0, _ufc_sb1, _ufc_sb2, _ufc_sb3};
 215 #endif
 216
 217 /*
 218  * eperm32tab: do 32 bit permutation and E selection
 219  *
 220  * The first index is the byte number in the 32 bit value to be permuted
 221  *  -  second  -   is the value of this byte
 222  *  -  third   -   selects the two 32 bit values
 223  *
 224  * The table is used and generated internally in init_des to speed it up
 225  */
 226 static ufc_long eperm32tab[4][256][2];
 227
 228 /*
 229  * do_pc1: permform pc1 permutation in the key schedule generation.
 230  *
 231  * The first   index is the byte number in the 8 byte ASCII key
 232  *  -  second    -      -    the two 28 bits halfs of the result
 233  *  -  third     -   selects the 7 bits actually used of each byte
 234  *
 235  * The result is kept with 28 bit per 32 bit with the 4 most significant
 236  * bits zero.
 237  */
 238 static ufc_long do_pc1[8][2][128];
 239
 240 /*
 241  * do_pc2: permform pc2 permutation in the key schedule generation.
 242  *
 243  * The first   index is the septet number in the two 28 bit intermediate values
 244  *  -  second    -    -  -  septet values
 245  *
 246  * Knowledge of the structure of the pc2 permutation is used.
 247  *
 248  * The result is kept with 28 bit per 32 bit with the 4 most significant
 249  * bits zero.
 250  */
 251 static ufc_long do_pc2[8][128];
 252
 253 /*
 254  * efp: undo an extra e selection and do final
 255  *      permutation giving the DES result.
 256  *
 257  *      Invoked 6 bit a time on two 48 bit values
 258  *      giving two 32 bit longs.
 259  */
 260 static ufc_long efp[16][64][2];
 261
 262 static unsigned char bytemask[8]  = {
 263   0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
 264 };
 265
 266 static ufc_long longmask[32] = {
 267   0x80000000, 0x40000000, 0x20000000, 0x10000000,
 268   0x08000000, 0x04000000, 0x02000000, 0x01000000,
 269   0x00800000, 0x00400000, 0x00200000, 0x00100000,
 270   0x00080000, 0x00040000, 0x00020000, 0x00010000,
 271   0x00008000, 0x00004000, 0x00002000, 0x00001000,
 272   0x00000800, 0x00000400, 0x00000200, 0x00000100,
 273   0x00000080, 0x00000040, 0x00000020, 0x00000010,
 274   0x00000008, 0x00000004, 0x00000002, 0x00000001
 275 };
 276
 277
 278 /*
 279  * Silly rewrite of 'bzero'. I do so
 280  * because some machines don't have
 281  * bzero and some don't have memset.
 282  */
 283
 284 static void clearmem(char *start, int cnt)
 285   { while(cnt--)
 286       *start++ = '\0';
 287   }
 288
 289 static int initialized = 0;
 290
 291 /* lookup a 6 bit value in sbox */
 292
 293 #define s_lookup(i,s) sbox[(i)][(((s)>>4) & 0x2)|((s) & 0x1)][((s)>>1) & 0xf];
 294
 295 /*
 296  * Initialize unit - may be invoked directly
 297  * by fcrypt users.
 298  */
 299
 300 static void ufc_init_des(void)
 301   { int comes_from_bit;
 302     int bit, sg;
 303     ufc_long j;
 304     ufc_long mask1, mask2;
 305
 306     /*
 307      * Create the do_pc1 table used
 308      * to affect pc1 permutation
 309      * when generating keys
 310      */
 311     for(bit = 0; bit < 56; bit++) {
 312       comes_from_bit  = pc1[bit] - 1;
 313       mask1 = bytemask[comes_from_bit % 8 + 1];
 314       mask2 = longmask[bit % 28 + 4];
 315       for(j = 0; j < 128; j++) {
 316         if(j & mask1)
 317           do_pc1[comes_from_bit / 8][bit / 28][j] |= mask2;
 318       }
 319     }
 320
 321     /*
 322      * Create the do_pc2 table used
 323      * to affect pc2 permutation when
 324      * generating keys
 325      */
 326     for(bit = 0; bit < 48; bit++) {
 327       comes_from_bit  = pc2[bit] - 1;
 328       mask1 = bytemask[comes_from_bit % 7 + 1];
 329       mask2 = BITMASK(bit % 24);
 330       for(j = 0; j < 128; j++) {
 331         if(j & mask1)
 332           do_pc2[comes_from_bit / 7][j] |= mask2;
 333       }
 334     }
 335
 336     /*
 337      * Now generate the table used to do combined
 338      * 32 bit permutation and e expansion
 339      *
 340      * We use it because we have to permute 16384 32 bit
 341      * longs into 48 bit in order to initialize sb.
 342      *
 343      * Looping 48 rounds per permutation becomes
 344      * just too slow...
 345      *
 346      */
 347
 348     clearmem((char*)eperm32tab, sizeof(eperm32tab));
 349
 350     for(bit = 0; bit < 48; bit++) {
 351       ufc_long inner_mask1,comes_from;
 352
 353       comes_from = perm32[esel[bit]-1]-1;
 354       inner_mask1      = bytemask[comes_from % 8];
 355
 356       for(j = 256; j--;) {
 357         if(j & inner_mask1)
 358           eperm32tab[comes_from / 8][j][bit / 24] |= BITMASK(bit % 24);
 359       }
 360     }
 361
 362     /*
 363      * Create the sb tables:
 364      *
 365      * For each 12 bit segment of an 48 bit intermediate
 366      * result, the sb table precomputes the two 4 bit
 367      * values of the sbox lookups done with the two 6
 368      * bit halves, shifts them to their proper place,
 369      * sends them through perm32 and finally E expands
 370      * them so that they are ready for the next
 371      * DES round.
 372      *
 373      */
 374     for(sg = 0; sg < 4; sg++) {
 375       int j1, j2;
 376       int s1, s2;
 377
 378       for(j1 = 0; j1 < 64; j1++) {
 379         s1 = s_lookup(2 * sg, j1);
 380         for(j2 = 0; j2 < 64; j2++) {
 381           ufc_long to_permute, inx;
 382
 383           s2         = s_lookup(2 * sg + 1, j2);
 384           to_permute = ((s1 << 4)  | s2) << (24 - 8 * sg);
 385
 386 #ifdef _UFC_32_
 387           inx = ((j1 << 6)  | j2) << 1;
 388           sb[sg][inx  ]  = eperm32tab[0][(to_permute >> 24) & 0xff][0];
 389           sb[sg][inx+1]  = eperm32tab[0][(to_permute >> 24) & 0xff][1];
 390           sb[sg][inx  ] |= eperm32tab[1][(to_permute >> 16) & 0xff][0];
 391           sb[sg][inx+1] |= eperm32tab[1][(to_permute >> 16) & 0xff][1];
 392           sb[sg][inx  ] |= eperm32tab[2][(to_permute >>  8) & 0xff][0];
 393           sb[sg][inx+1] |= eperm32tab[2][(to_permute >>  8) & 0xff][1];
 394           sb[sg][inx  ] |= eperm32tab[3][(to_permute)       & 0xff][0];
 395           sb[sg][inx+1] |= eperm32tab[3][(to_permute)       & 0xff][1];
 396 #endif
 397 #ifdef _UFC_64_
 398           inx = ((j1 << 6)  | j2);
 399           sb[sg][inx]  =
 400             ((long64)eperm32tab[0][(to_permute >> 24) & 0xff][0] << 32) |
 401              (long64)eperm32tab[0][(to_permute >> 24) & 0xff][1];
 402           sb[sg][inx] |=
 403             ((long64)eperm32tab[1][(to_permute >> 16) & 0xff][0] << 32) |
 404              (long64)eperm32tab[1][(to_permute >> 16) & 0xff][1];
 405           sb[sg][inx] |=
 406             ((long64)eperm32tab[2][(to_permute >>  8) & 0xff][0] << 32) |
 407              (long64)eperm32tab[2][(to_permute >>  8) & 0xff][1];
 408           sb[sg][inx] |=
 409             ((long64)eperm32tab[3][(to_permute)       & 0xff][0] << 32) |
 410              (long64)eperm32tab[3][(to_permute)       & 0xff][1];
 411 #endif
 412         }
 413       }
 414     }
 415
 416     /*
 417      * Create an inverse matrix for esel telling
 418      * where to plug out bits if undoing it
 419      */
 420     for(bit=48; bit--;) {
 421       e_inverse[esel[bit] - 1     ] = bit;
 422       e_inverse[esel[bit] - 1 + 32] = bit + 48;
 423     }
 424
 425     /*
 426      * create efp: the matrix used to
 427      * undo the E expansion and effect final permutation
 428      */
 429     clearmem((char*)efp, sizeof efp);
 430     for(bit = 0; bit < 64; bit++) {
 431       int o_bit, o_long;
 432       ufc_long word_value, inner_mask1, inner_mask2;
 433       int comes_from_f_bit, comes_from_e_bit;
 434       int comes_from_word, bit_within_word;
 435
 436       /* See where bit i belongs in the two 32 bit long's */
 437       o_long = bit / 32; /* 0..1  */
 438       o_bit  = bit % 32; /* 0..31 */
 439
 440       /*
 441        * And find a bit in the e permutated value setting this bit.
 442        *
 443        * Note: the e selection may have selected the same bit several
 444        * times. By the initialization of e_inverse, we only look
 445        * for one specific instance.
 446        */
 447       comes_from_f_bit = final_perm[bit] - 1;         /* 0..63 */
 448       comes_from_e_bit = e_inverse[comes_from_f_bit]; /* 0..95 */
 449       comes_from_word  = comes_from_e_bit / 6;        /* 0..15 */
 450       bit_within_word  = comes_from_e_bit % 6;        /* 0..5  */
 451
 452       inner_mask1 = longmask[bit_within_word + 26];
 453       inner_mask2 = longmask[o_bit];
 454
 455       for(word_value = 64; word_value--;) {
 456         if(word_value & inner_mask1)
 457           efp[comes_from_word][word_value][o_long] |= inner_mask2;
 458       }
 459     }
 460     initialized++;
 461   }
 462
 463 /*
 464  * Process the elements of the sb table permuting the
 465  * bits swapped in the expansion by the current salt.
 466  */
 467
 468 #ifdef _UFC_32_
 469 static void shuffle_sb(long32 *k, ufc_long saltbits)
 470   { ufc_long j;
 471     long32 x;
 472     for(j=4096; j--;) {
 473       x = (k[0] ^ k[1]) & (long32)saltbits;
 474       *k++ ^= x;
 475       *k++ ^= x;
 476     }
 477   }
 478 #endif
 479
 480 #ifdef _UFC_64_
 481 static void shuffle_sb(long64 *k, ufc_long saltbits)
 482   { ufc_long j;
 483     long64 x;
 484     for(j=4096; j--;) {
 485       x = ((*k >> 32) ^ *k) & (long64)saltbits;
 486       *k++ ^= (x << 32) | x;
 487     }
 488   }
 489 #endif
 490
 491 /*
 492  * Setup the unit for a new salt
 493  * Hopefully we'll not see a new salt in each crypt call.
 494  */
 495
 496 static unsigned char current_salt[3] = "&&"; /* invalid value */
 497 static ufc_long current_saltbits = 0;
 498 static int direction = 0;
 499
 500 static void setup_salt(const char *s1)
 501   { ufc_long i, j, saltbits;
 502     const unsigned char *s2 = (const unsigned char *)s1;
 503
 504     if(!initialized)
 505       ufc_init_des();
 506
 507     if(s2[0] == current_salt[0] && s2[1] == current_salt[1])
 508       return;
 509     current_salt[0] = s2[0]; current_salt[1] = s2[1];
 510
 511     /*
 512      * This is the only crypt change to DES:
 513      * entries are swapped in the expansion table
 514      * according to the bits set in the salt.
 515      */
 516     saltbits = 0;
 517     for(i = 0; i < 2; i++) {
 518       long c=ascii_to_bin(s2[i]);
 519       if(c < 0 || c > 63)
 520         c = 0;
 521       for(j = 0; j < 6; j++) {
 522         if((c >> j) & 0x1)
 523           saltbits |= BITMASK(6 * i + j);
 524       }
 525     }
 526
 527     /*
 528      * Permute the sb table values
 529      * to reflect the changed e
 530      * selection table
 531      */
 532     shuffle_sb(_ufc_sb0, current_saltbits ^ saltbits);
 533     shuffle_sb(_ufc_sb1, current_saltbits ^ saltbits);
 534     shuffle_sb(_ufc_sb2, current_saltbits ^ saltbits);
 535     shuffle_sb(_ufc_sb3, current_saltbits ^ saltbits);
 536
 537     current_saltbits = saltbits;
 538   }
 539
 540 static void ufc_mk_keytab(char *key)
 541   { ufc_long v1, v2, *k1;
 542     int i;
 543 #ifdef _UFC_32_
 544     long32 v, *k2 = &_ufc_keytab[0][0];
 545 #endif
 546 #ifdef _UFC_64_
 547     long64 v, *k2 = &_ufc_keytab[0];
 548 #endif
 549
 550     v1 = v2 = 0; k1 = &do_pc1[0][0][0];
 551     for(i = 8; i--;) {
 552       v1 |= k1[*key   & 0x7f]; k1 += 128;
 553       v2 |= k1[*key++ & 0x7f]; k1 += 128;
 554     }
 555
 556     for(i = 0; i < 16; i++) {
 557       k1 = &do_pc2[0][0];
 558
 559       v1 = (v1 << rots[i]) | (v1 >> (28 - rots[i]));
 560       v  = k1[(v1 >> 21) & 0x7f]; k1 += 128;
 561       v |= k1[(v1 >> 14) & 0x7f]; k1 += 128;
 562       v |= k1[(v1 >>  7) & 0x7f]; k1 += 128;
 563       v |= k1[(v1      ) & 0x7f]; k1 += 128;
 564
 565 #ifdef _UFC_32_
 566       *k2++ = v;
 567       v = 0;
 568 #endif
 569 #ifdef _UFC_64_
 570       v <<= 32;
 571 #endif
 572
 573       v2 = (v2 << rots[i]) | (v2 >> (28 - rots[i]));
 574       v |= k1[(v2 >> 21) & 0x7f]; k1 += 128;
 575       v |= k1[(v2 >> 14) & 0x7f]; k1 += 128;
 576       v |= k1[(v2 >>  7) & 0x7f]; k1 += 128;
 577       v |= k1[(v2      ) & 0x7f];
 578
 579       *k2++ = v;
 580     }
 581
 582     direction = 0;
 583   }
 584
 585 /*
 586  * Undo an extra E selection and do final permutations
 587  */
 588
 589 ufc_long *_ufc_dofinalperm(ufc_long l1, ufc_long l2, ufc_long r1, ufc_long r2)
 590   { ufc_long v1, v2, x;
 591     static ufc_long ary[2];
 592
 593     x = (l1 ^ l2) & current_saltbits; l1 ^= x; l2 ^= x;
 594     x = (r1 ^ r2) & current_saltbits; r1 ^= x; r2 ^= x;
 595
 596     v1=v2=0; l1 >>= 3; l2 >>= 3; r1 >>= 3; r2 >>= 3;
 597
 598     v1 |= efp[15][ r2         & 0x3f][0]; v2 |= efp[15][ r2 & 0x3f][1];
 599     v1 |= efp[14][(r2 >>= 6)  & 0x3f][0]; v2 |= efp[14][ r2 & 0x3f][1];
 600     v1 |= efp[13][(r2 >>= 10) & 0x3f][0]; v2 |= efp[13][ r2 & 0x3f][1];
 601     v1 |= efp[12][(r2 >>= 6)  & 0x3f][0]; v2 |= efp[12][ r2 & 0x3f][1];
 602
 603     v1 |= efp[11][ r1         & 0x3f][0]; v2 |= efp[11][ r1 & 0x3f][1];
 604     v1 |= efp[10][(r1 >>= 6)  & 0x3f][0]; v2 |= efp[10][ r1 & 0x3f][1];
 605     v1 |= efp[ 9][(r1 >>= 10) & 0x3f][0]; v2 |= efp[ 9][ r1 & 0x3f][1];
 606     v1 |= efp[ 8][(r1 >>= 6)  & 0x3f][0]; v2 |= efp[ 8][ r1 & 0x3f][1];
 607
 608     v1 |= efp[ 7][ l2         & 0x3f][0]; v2 |= efp[ 7][ l2 & 0x3f][1];
 609     v1 |= efp[ 6][(l2 >>= 6)  & 0x3f][0]; v2 |= efp[ 6][ l2 & 0x3f][1];
 610     v1 |= efp[ 5][(l2 >>= 10) & 0x3f][0]; v2 |= efp[ 5][ l2 & 0x3f][1];
 611     v1 |= efp[ 4][(l2 >>= 6)  & 0x3f][0]; v2 |= efp[ 4][ l2 & 0x3f][1];
 612
 613     v1 |= efp[ 3][ l1         & 0x3f][0]; v2 |= efp[ 3][ l1 & 0x3f][1];
 614     v1 |= efp[ 2][(l1 >>= 6)  & 0x3f][0]; v2 |= efp[ 2][ l1 & 0x3f][1];
 615     v1 |= efp[ 1][(l1 >>= 10) & 0x3f][0]; v2 |= efp[ 1][ l1 & 0x3f][1];
 616     v1 |= efp[ 0][(l1 >>= 6)  & 0x3f][0]; v2 |= efp[ 0][ l1 & 0x3f][1];
 617
 618     ary[0] = v1; ary[1] = v2;
 619     return ary;
 620   }
 621
 622 /*
 623  * crypt only: convert from 64 bit to 11 bit ASCII
 624  * prefixing with the salt
 625  */
 626
 627 static char *output_conversion(ufc_long v1, ufc_long v2, const char *salt)
 628   { static char outbuf[14];
 629     int i, s;
 630
 631     outbuf[0] = salt[0];
 632     outbuf[1] = salt[1] ? salt[1] : salt[0];
 633
 634     for(i = 0; i < 5; i++)
 635       outbuf[i + 2] = bin_to_ascii((v1 >> (26 - 6 * i)) & 0x3f);
 636
 637     s  = (v2 & 0xf) << 2;
 638     v2 = (v2 >> 2) | ((v1 & 0x3) << 30);
 639
 640     for(i = 5; i < 10; i++)
 641       outbuf[i + 2] = bin_to_ascii((v2 >> (56 - 6 * i)) & 0x3f);
 642
 643     outbuf[12] = bin_to_ascii(s);
 644     outbuf[13] = 0;
 645
 646     return outbuf;
 647   }
 648
 649 /*
 650  * UNIX crypt function
 651  */
 652
 653 static ufc_long *_ufc_doit(ufc_long , ufc_long, ufc_long, ufc_long, ufc_long);
 654
 655 char *ufc_crypt(const char *key,const char *salt)
 656   { ufc_long *s;
 657     char ktab[9];
 658
 659     /*
 660      * Hack DES tables according to salt
 661      */
 662     setup_salt(salt);
 663
 664     /*
 665      * Setup key schedule
 666      */
 667     clearmem(ktab, sizeof ktab);
 668     strncpy(ktab, key, 8);
 669     ufc_mk_keytab(ktab);
 670
 671     /*
 672      * Go for the 25 DES encryptions
 673      */
 674     s = _ufc_doit((ufc_long)0, (ufc_long)0,
 675                   (ufc_long)0, (ufc_long)0, (ufc_long)25);
 676
 677     /*
 678      * And convert back to 6 bit ASCII
 679      */
 680     return output_conversion(s[0], s[1], salt);
 681   }
 682
 683
 684 #ifdef _UFC_32_
 685
 686 /*
 687  * 32 bit version
 688  */
 689
 690 extern long32 _ufc_keytab[16][2];
 691 extern long32 _ufc_sb0[], _ufc_sb1[], _ufc_sb2[], _ufc_sb3[];
 692
 693 #define SBA(sb, v) (*(long32*)((char*)(sb)+(v)))
 694
 695 static ufc_long *_ufc_doit(ufc_long l1, ufc_long l2, ufc_long r1, ufc_long r2, ufc_long itr)
 696   { int i;
 697     long32 s, *k;
 698
 699     while(itr--) {
 700       k = &_ufc_keytab[0][0];
 701       for(i=8; i--; ) {
 702         s = *k++ ^ r1;
 703         l1 ^= SBA(_ufc_sb1, s & 0xffff); l2 ^= SBA(_ufc_sb1, (s & 0xffff)+4);
 704         l1 ^= SBA(_ufc_sb0, s >>= 16);   l2 ^= SBA(_ufc_sb0, (s)         +4);
 705         s = *k++ ^ r2;
 706         l1 ^= SBA(_ufc_sb3, s & 0xffff); l2 ^= SBA(_ufc_sb3, (s & 0xffff)+4);
 707         l1 ^= SBA(_ufc_sb2, s >>= 16);   l2 ^= SBA(_ufc_sb2, (s)         +4);
 708
 709         s = *k++ ^ l1;
 710         r1 ^= SBA(_ufc_sb1, s & 0xffff); r2 ^= SBA(_ufc_sb1, (s & 0xffff)+4);
 711         r1 ^= SBA(_ufc_sb0, s >>= 16);   r2 ^= SBA(_ufc_sb0, (s)         +4);
 712         s = *k++ ^ l2;
 713         r1 ^= SBA(_ufc_sb3, s & 0xffff); r2 ^= SBA(_ufc_sb3, (s & 0xffff)+4);
 714         r1 ^= SBA(_ufc_sb2, s >>= 16);   r2 ^= SBA(_ufc_sb2, (s)         +4);
 715       }
 716       s=l1; l1=r1; r1=s; s=l2; l2=r2; r2=s;
 717     }
 718     return _ufc_dofinalperm(l1, l2, r1, r2);
 719   }
 720
 721 #endif
 722
 723 #ifdef _UFC_64_
 724
 725 /*
 726  * 64 bit version
 727  */
 728
 729 extern long64 _ufc_keytab[16];
 730 extern long64 _ufc_sb0[], _ufc_sb1[], _ufc_sb2[], _ufc_sb3[];
 731
 732 #define SBA(sb, v) (*(long64*)((char*)(sb)+(v)))
 733
 734 static ufc_long *_ufc_doit(ufc_long l1, ufc_long l2, ufc_long r1, ufc_long r2, ufc_long itr)
 735   { int i;
 736     long64 l, r, s, *k;
 737
 738     l = (((long64)l1) << 32) | ((long64)l2);
 739     r = (((long64)r1) << 32) | ((long64)r2);
 740
 741     while(itr--) {
 742       k = &_ufc_keytab[0];
 743       for(i=8; i--; ) {
 744         s = *k++ ^ r;
 745         l ^= SBA(_ufc_sb3, (s >>  0) & 0xffff);
 746         l ^= SBA(_ufc_sb2, (s >> 16) & 0xffff);
 747         l ^= SBA(_ufc_sb1, (s >> 32) & 0xffff);
 748         l ^= SBA(_ufc_sb0, (s >> 48) & 0xffff);
 749
 750         s = *k++ ^ l;
 751         r ^= SBA(_ufc_sb3, (s >>  0) & 0xffff);
 752         r ^= SBA(_ufc_sb2, (s >> 16) & 0xffff);
 753         r ^= SBA(_ufc_sb1, (s >> 32) & 0xffff);
 754         r ^= SBA(_ufc_sb0, (s >> 48) & 0xffff);
 755       }
 756       s=l; l=r; r=s;
 757     }
 758
 759     l1 = l >> 32; l2 = l & 0xffffffff;
 760     r1 = r >> 32; r2 = r & 0xffffffff;
 761     return _ufc_dofinalperm(l1, l2, r1, r2);
 762   }
 763
 764 #endif
 765
 766
 767 #else
 768  int ufc_dummy_procedure(void);
 769  int ufc_dummy_procedure(void) {return 0;}
 770 #endif