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