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(char *start, int cnt)
 286   { while(cnt--)
 287       *start++ = '\0';
 288   }
 289
 290 static int initialized = 0;
 291
 292 /* lookup a 6 bit value in sbox */
 293
 294 #define s_lookup(i,s) sbox[(i)][(((s)>>4) & 0x2)|((s) & 0x1)][((s)>>1) & 0xf];
 295
 296 /*
 297  * Initialize unit - may be invoked directly
 298  * by fcrypt users.
 299  */
 300
 301 static void ufc_init_des(void)
 302   { int comes_from_bit;
 303     int bit, sg;
 304     ufc_long j;
 305     ufc_long mask1, mask2;
 306
 307     /*
 308      * Create the do_pc1 table used
 309      * to affect pc1 permutation
 310      * when generating keys
 311      */
 312     for(bit = 0; bit < 56; bit++) {
 313       comes_from_bit  = pc1[bit] - 1;
 314       mask1 = bytemask[comes_from_bit % 8 + 1];
 315       mask2 = longmask[bit % 28 + 4];
 316       for(j = 0; j < 128; j++) {
 317         if(j & mask1)
 318           do_pc1[comes_from_bit / 8][bit / 28][j] |= mask2;
 319       }
 320     }
 321
 322     /*
 323      * Create the do_pc2 table used
 324      * to affect pc2 permutation when
 325      * generating keys
 326      */
 327     for(bit = 0; bit < 48; bit++) {
 328       comes_from_bit  = pc2[bit] - 1;
 329       mask1 = bytemask[comes_from_bit % 7 + 1];
 330       mask2 = BITMASK(bit % 24);
 331       for(j = 0; j < 128; j++) {
 332         if(j & mask1)
 333           do_pc2[comes_from_bit / 7][j] |= mask2;
 334       }
 335     }
 336
 337     /*
 338      * Now generate the table used to do combined
 339      * 32 bit permutation and e expansion
 340      *
 341      * We use it because we have to permute 16384 32 bit
 342      * longs into 48 bit in order to initialize sb.
 343      *
 344      * Looping 48 rounds per permutation becomes
 345      * just too slow...
 346      *
 347      */
 348
 349     clearmem((char*)eperm32tab, sizeof(eperm32tab));
 350
 351     for(bit = 0; bit < 48; bit++) {
 352       ufc_long inner_mask1,comes_from;
 353
 354       comes_from = perm32[esel[bit]-1]-1;
 355       inner_mask1      = bytemask[comes_from % 8];
 356
 357       for(j = 256; j--;) {
 358         if(j & inner_mask1)
 359           eperm32tab[comes_from / 8][j][bit / 24] |= BITMASK(bit % 24);
 360       }
 361     }
 362
 363     /*
 364      * Create the sb tables:
 365      *
 366      * For each 12 bit segment of an 48 bit intermediate
 367      * result, the sb table precomputes the two 4 bit
 368      * values of the sbox lookups done with the two 6
 369      * bit halves, shifts them to their proper place,
 370      * sends them through perm32 and finally E expands
 371      * them so that they are ready for the next
 372      * DES round.
 373      *
 374      */
 375     for(sg = 0; sg < 4; sg++) {
 376       int j1, j2;
 377       int s1, s2;
 378
 379       for(j1 = 0; j1 < 64; j1++) {
 380         s1 = s_lookup(2 * sg, j1);
 381         for(j2 = 0; j2 < 64; j2++) {
 382           ufc_long to_permute, inx;
 383
 384           s2         = s_lookup(2 * sg + 1, j2);
 385           to_permute = ((s1 << 4)  | s2) << (24 - 8 * sg);
 386
 387 #ifdef _UFC_32_
 388           inx = ((j1 << 6)  | j2) << 1;
 389           sb[sg][inx  ]  = eperm32tab[0][(to_permute >> 24) & 0xff][0];
 390           sb[sg][inx+1]  = eperm32tab[0][(to_permute >> 24) & 0xff][1];
 391           sb[sg][inx  ] |= eperm32tab[1][(to_permute >> 16) & 0xff][0];
 392           sb[sg][inx+1] |= eperm32tab[1][(to_permute >> 16) & 0xff][1];
 393           sb[sg][inx  ] |= eperm32tab[2][(to_permute >>  8) & 0xff][0];
 394           sb[sg][inx+1] |= eperm32tab[2][(to_permute >>  8) & 0xff][1];
 395           sb[sg][inx  ] |= eperm32tab[3][(to_permute)       & 0xff][0];
 396           sb[sg][inx+1] |= eperm32tab[3][(to_permute)       & 0xff][1];
 397 #endif
 398 #ifdef _UFC_64_
 399           inx = ((j1 << 6)  | j2);
 400           sb[sg][inx]  =
 401             ((long64)eperm32tab[0][(to_permute >> 24) & 0xff][0] << 32) |
 402              (long64)eperm32tab[0][(to_permute >> 24) & 0xff][1];
 403           sb[sg][inx] |=
 404             ((long64)eperm32tab[1][(to_permute >> 16) & 0xff][0] << 32) |
 405              (long64)eperm32tab[1][(to_permute >> 16) & 0xff][1];
 406           sb[sg][inx] |=
 407             ((long64)eperm32tab[2][(to_permute >>  8) & 0xff][0] << 32) |
 408              (long64)eperm32tab[2][(to_permute >>  8) & 0xff][1];
 409           sb[sg][inx] |=
 410             ((long64)eperm32tab[3][(to_permute)       & 0xff][0] << 32) |
 411              (long64)eperm32tab[3][(to_permute)       & 0xff][1];
 412 #endif
 413         }
 414       }
 415     }
 416
 417     /*
 418      * Create an inverse matrix for esel telling
 419      * where to plug out bits if undoing it
 420      */
 421     for(bit=48; bit--;) {
 422       e_inverse[esel[bit] - 1     ] = bit;
 423       e_inverse[esel[bit] - 1 + 32] = bit + 48;
 424     }
 425
 426     /*
 427      * create efp: the matrix used to
 428      * undo the E expansion and effect final permutation
 429      */
 430     clearmem((char*)efp, sizeof efp);
 431     for(bit = 0; bit < 64; bit++) {
 432       int o_bit, o_long;
 433       ufc_long word_value, inner_mask1, inner_mask2;
 434       int comes_from_f_bit, comes_from_e_bit;
 435       int comes_from_word, bit_within_word;
 436
 437       /* See where bit i belongs in the two 32 bit long's */
 438       o_long = bit / 32; /* 0..1  */
 439       o_bit  = bit % 32; /* 0..31 */
 440
 441       /*
 442        * And find a bit in the e permutated value setting this bit.
 443        *
 444        * Note: the e selection may have selected the same bit several
 445        * times. By the initialization of e_inverse, we only look
 446        * for one specific instance.
 447        */
 448       comes_from_f_bit = final_perm[bit] - 1;         /* 0..63 */
 449       comes_from_e_bit = e_inverse[comes_from_f_bit]; /* 0..95 */
 450       comes_from_word  = comes_from_e_bit / 6;        /* 0..15 */
 451       bit_within_word  = comes_from_e_bit % 6;        /* 0..5  */
 452
 453       inner_mask1 = longmask[bit_within_word + 26];
 454       inner_mask2 = longmask[o_bit];
 455
 456       for(word_value = 64; word_value--;) {
 457         if(word_value & inner_mask1)
 458           efp[comes_from_word][word_value][o_long] |= inner_mask2;
 459       }
 460     }
 461     initialized++;
 462   }
 463
 464 /*
 465  * Process the elements of the sb table permuting the
 466  * bits swapped in the expansion by the current salt.
 467  */
 468
 469 #ifdef _UFC_32_
 470 static void shuffle_sb(long32 *k, ufc_long saltbits)
 471   { ufc_long j;
 472     long32 x;
 473     for(j=4096; j--;) {
 474       x = (k[0] ^ k[1]) & (long32)saltbits;
 475       *k++ ^= x;
 476       *k++ ^= x;
 477     }
 478   }
 479 #endif
 480
 481 #ifdef _UFC_64_
 482 static void shuffle_sb(long64 *k, ufc_long saltbits)
 483   { ufc_long j;
 484     long64 x;
 485     for(j=4096; j--;) {
 486       x = ((*k >> 32) ^ *k) & (long64)saltbits;
 487       *k++ ^= (x << 32) | x;
 488     }
 489   }
 490 #endif
 491
 492 /*
 493  * Setup the unit for a new salt
 494  * Hopefully we'll not see a new salt in each crypt call.
 495  */
 496
 497 static unsigned char current_salt[3] = "&&"; /* invalid value */
 498 static ufc_long current_saltbits = 0;
 499 static int direction = 0;
 500
 501 static void setup_salt(const char *s1)
 502   { ufc_long i, j, saltbits;
 503     const unsigned char *s2 = (const unsigned char *)s1;
 504
 505     if(!initialized)
 506       ufc_init_des();
 507
 508     if(s2[0] == current_salt[0] && s2[1] == current_salt[1])
 509       return;
 510     current_salt[0] = s2[0]; current_salt[1] = s2[1];
 511
 512     /*
 513      * This is the only crypt change to DES:
 514      * entries are swapped in the expansion table
 515      * according to the bits set in the salt.
 516      */
 517     saltbits = 0;
 518     for(i = 0; i < 2; i++) {
 519       long c=ascii_to_bin(s2[i]);
 520       if(c < 0 || c > 63)
 521         c = 0;
 522       for(j = 0; j < 6; j++) {
 523         if((c >> j) & 0x1)
 524           saltbits |= BITMASK(6 * i + j);
 525       }
 526     }
 527
 528     /*
 529      * Permute the sb table values
 530      * to reflect the changed e
 531      * selection table
 532      */
 533     shuffle_sb(_ufc_sb0, current_saltbits ^ saltbits);
 534     shuffle_sb(_ufc_sb1, current_saltbits ^ saltbits);
 535     shuffle_sb(_ufc_sb2, current_saltbits ^ saltbits);
 536     shuffle_sb(_ufc_sb3, current_saltbits ^ saltbits);
 537
 538     current_saltbits = saltbits;
 539   }
 540
 541 static void ufc_mk_keytab(char *key)
 542   { ufc_long v1, v2, *k1;
 543     int i;
 544 #ifdef _UFC_32_
 545     long32 v, *k2 = &_ufc_keytab[0][0];
 546 #endif
 547 #ifdef _UFC_64_
 548     long64 v, *k2 = &_ufc_keytab[0];
 549 #endif
 550
 551     v1 = v2 = 0; k1 = &do_pc1[0][0][0];
 552     for(i = 8; i--;) {
 553       v1 |= k1[*key   & 0x7f]; k1 += 128;
 554       v2 |= k1[*key++ & 0x7f]; k1 += 128;
 555     }
 556
 557     for(i = 0; i < 16; i++) {
 558       k1 = &do_pc2[0][0];
 559
 560       v1 = (v1 << rots[i]) | (v1 >> (28 - rots[i]));
 561       v  = k1[(v1 >> 21) & 0x7f]; k1 += 128;
 562       v |= k1[(v1 >> 14) & 0x7f]; k1 += 128;
 563       v |= k1[(v1 >>  7) & 0x7f]; k1 += 128;
 564       v |= k1[(v1      ) & 0x7f]; k1 += 128;
 565
 566 #ifdef _UFC_32_
 567       *k2++ = v;
 568       v = 0;
 569 #endif
 570 #ifdef _UFC_64_
 571       v <<= 32;
 572 #endif
 573
 574       v2 = (v2 << rots[i]) | (v2 >> (28 - rots[i]));
 575       v |= k1[(v2 >> 21) & 0x7f]; k1 += 128;
 576       v |= k1[(v2 >> 14) & 0x7f]; k1 += 128;
 577       v |= k1[(v2 >>  7) & 0x7f]; k1 += 128;
 578       v |= k1[(v2      ) & 0x7f];
 579
 580       *k2++ = v;
 581     }
 582
 583     direction = 0;
 584   }
 585
 586 /*
 587  * Undo an extra E selection and do final permutations
 588  */
 589
 590 ufc_long *_ufc_dofinalperm(ufc_long l1, ufc_long l2, ufc_long r1, ufc_long r2)
 591   { ufc_long v1, v2, x;
 592     static ufc_long ary[2];
 593
 594     x = (l1 ^ l2) & current_saltbits; l1 ^= x; l2 ^= x;
 595     x = (r1 ^ r2) & current_saltbits; r1 ^= x; r2 ^= x;
 596
 597     v1=v2=0; l1 >>= 3; l2 >>= 3; r1 >>= 3; r2 >>= 3;
 598
 599     v1 |= efp[15][ r2         & 0x3f][0]; v2 |= efp[15][ r2 & 0x3f][1];
 600     v1 |= efp[14][(r2 >>= 6)  & 0x3f][0]; v2 |= efp[14][ r2 & 0x3f][1];
 601     v1 |= efp[13][(r2 >>= 10) & 0x3f][0]; v2 |= efp[13][ r2 & 0x3f][1];
 602     v1 |= efp[12][(r2 >>= 6)  & 0x3f][0]; v2 |= efp[12][ r2 & 0x3f][1];
 603
 604     v1 |= efp[11][ r1         & 0x3f][0]; v2 |= efp[11][ r1 & 0x3f][1];
 605     v1 |= efp[10][(r1 >>= 6)  & 0x3f][0]; v2 |= efp[10][ r1 & 0x3f][1];
 606     v1 |= efp[ 9][(r1 >>= 10) & 0x3f][0]; v2 |= efp[ 9][ r1 & 0x3f][1];
 607     v1 |= efp[ 8][(r1 >>= 6)  & 0x3f][0]; v2 |= efp[ 8][ r1 & 0x3f][1];
 608
 609     v1 |= efp[ 7][ l2         & 0x3f][0]; v2 |= efp[ 7][ l2 & 0x3f][1];
 610     v1 |= efp[ 6][(l2 >>= 6)  & 0x3f][0]; v2 |= efp[ 6][ l2 & 0x3f][1];
 611     v1 |= efp[ 5][(l2 >>= 10) & 0x3f][0]; v2 |= efp[ 5][ l2 & 0x3f][1];
 612     v1 |= efp[ 4][(l2 >>= 6)  & 0x3f][0]; v2 |= efp[ 4][ l2 & 0x3f][1];
 613
 614     v1 |= efp[ 3][ l1         & 0x3f][0]; v2 |= efp[ 3][ l1 & 0x3f][1];
 615     v1 |= efp[ 2][(l1 >>= 6)  & 0x3f][0]; v2 |= efp[ 2][ l1 & 0x3f][1];
 616     v1 |= efp[ 1][(l1 >>= 10) & 0x3f][0]; v2 |= efp[ 1][ l1 & 0x3f][1];
 617     v1 |= efp[ 0][(l1 >>= 6)  & 0x3f][0]; v2 |= efp[ 0][ l1 & 0x3f][1];
 618
 619     ary[0] = v1; ary[1] = v2;
 620     return ary;
 621   }
 622
 623 /*
 624  * crypt only: convert from 64 bit to 11 bit ASCII
 625  * prefixing with the salt
 626  */
 627
 628 static char *output_conversion(ufc_long v1, ufc_long v2, const char *salt)
 629   { static char outbuf[14];
 630     int i, s;
 631
 632     outbuf[0] = salt[0];
 633     outbuf[1] = salt[1] ? salt[1] : salt[0];
 634
 635     for(i = 0; i < 5; i++)
 636       outbuf[i + 2] = bin_to_ascii((v1 >> (26 - 6 * i)) & 0x3f);
 637
 638     s  = (v2 & 0xf) << 2;
 639     v2 = (v2 >> 2) | ((v1 & 0x3) << 30);
 640
 641     for(i = 5; i < 10; i++)
 642       outbuf[i + 2] = bin_to_ascii((v2 >> (56 - 6 * i)) & 0x3f);
 643
 644     outbuf[12] = bin_to_ascii(s);
 645     outbuf[13] = 0;
 646
 647     return outbuf;
 648   }
 649
 650 /*
 651  * UNIX crypt function
 652  */
 653
 654 static ufc_long *_ufc_doit(ufc_long , ufc_long, ufc_long, ufc_long, ufc_long);
 655
 656 char *ufc_crypt(const char *key,const char *salt)
 657   { ufc_long *s;
 658     char ktab[9];
 659
 660     /*
 661      * Hack DES tables according to salt
 662      */
 663     setup_salt(salt);
 664
 665     /*
 666      * Setup key schedule
 667      */
 668     clearmem(ktab, sizeof ktab);
 669     StrnCpy(ktab, key, 8);
 670     ufc_mk_keytab(ktab);
 671
 672     /*
 673      * Go for the 25 DES encryptions
 674      */
 675     s = _ufc_doit((ufc_long)0, (ufc_long)0,
 676                   (ufc_long)0, (ufc_long)0, (ufc_long)25);
 677
 678     /*
 679      * And convert back to 6 bit ASCII
 680      */
 681     return output_conversion(s[0], s[1], salt);
 682   }
 683
 684
 685 #ifdef _UFC_32_
 686
 687 /*
 688  * 32 bit version
 689  */
 690
 691 extern long32 _ufc_keytab[16][2];
 692 extern long32 _ufc_sb0[], _ufc_sb1[], _ufc_sb2[], _ufc_sb3[];
 693
 694 #define SBA(sb, v) (*(long32*)((char*)(sb)+(v)))
 695
 696 static ufc_long *_ufc_doit(ufc_long l1, ufc_long l2, ufc_long r1, ufc_long r2, ufc_long itr)
 697   { int i;
 698     long32 s, *k;
 699
 700     while(itr--) {
 701       k = &_ufc_keytab[0][0];
 702       for(i=8; i--; ) {
 703         s = *k++ ^ r1;
 704         l1 ^= SBA(_ufc_sb1, s & 0xffff); l2 ^= SBA(_ufc_sb1, (s & 0xffff)+4);
 705         l1 ^= SBA(_ufc_sb0, s >>= 16);   l2 ^= SBA(_ufc_sb0, (s)         +4);
 706         s = *k++ ^ r2;
 707         l1 ^= SBA(_ufc_sb3, s & 0xffff); l2 ^= SBA(_ufc_sb3, (s & 0xffff)+4);
 708         l1 ^= SBA(_ufc_sb2, s >>= 16);   l2 ^= SBA(_ufc_sb2, (s)         +4);
 709
 710         s = *k++ ^ l1;
 711         r1 ^= SBA(_ufc_sb1, s & 0xffff); r2 ^= SBA(_ufc_sb1, (s & 0xffff)+4);
 712         r1 ^= SBA(_ufc_sb0, s >>= 16);   r2 ^= SBA(_ufc_sb0, (s)         +4);
 713         s = *k++ ^ l2;
 714         r1 ^= SBA(_ufc_sb3, s & 0xffff); r2 ^= SBA(_ufc_sb3, (s & 0xffff)+4);
 715         r1 ^= SBA(_ufc_sb2, s >>= 16);   r2 ^= SBA(_ufc_sb2, (s)         +4);
 716       }
 717       s=l1; l1=r1; r1=s; s=l2; l2=r2; r2=s;
 718     }
 719     return _ufc_dofinalperm(l1, l2, r1, r2);
 720   }
 721
 722 #endif
 723
 724 #ifdef _UFC_64_
 725
 726 /*
 727  * 64 bit version
 728  */
 729
 730 extern long64 _ufc_keytab[16];
 731 extern long64 _ufc_sb0[], _ufc_sb1[], _ufc_sb2[], _ufc_sb3[];
 732
 733 #define SBA(sb, v) (*(long64*)((char*)(sb)+(v)))
 734
 735 static ufc_long *_ufc_doit(ufc_long l1, ufc_long l2, ufc_long r1, ufc_long r2, ufc_long itr)
 736   { int i;
 737     long64 l, r, s, *k;
 738
 739     l = (((long64)l1) << 32) | ((long64)l2);
 740     r = (((long64)r1) << 32) | ((long64)r2);
 741
 742     while(itr--) {
 743       k = &_ufc_keytab[0];
 744       for(i=8; i--; ) {
 745         s = *k++ ^ r;
 746         l ^= SBA(_ufc_sb3, (s >>  0) & 0xffff);
 747         l ^= SBA(_ufc_sb2, (s >> 16) & 0xffff);
 748         l ^= SBA(_ufc_sb1, (s >> 32) & 0xffff);
 749         l ^= SBA(_ufc_sb0, (s >> 48) & 0xffff);
 750
 751         s = *k++ ^ l;
 752         r ^= SBA(_ufc_sb3, (s >>  0) & 0xffff);
 753         r ^= SBA(_ufc_sb2, (s >> 16) & 0xffff);
 754         r ^= SBA(_ufc_sb1, (s >> 32) & 0xffff);
 755         r ^= SBA(_ufc_sb0, (s >> 48) & 0xffff);
 756       }
 757       s=l; l=r; r=s;
 758     }
 759
 760     l1 = l >> 32; l2 = l & 0xffffffff;
 761     r1 = r >> 32; r2 = r & 0xffffffff;
 762     return _ufc_dofinalperm(l1, l2, r1, r2);
 763   }
 764
 765 #endif
 766
 767
 768 #else
 769  int ufc_dummy_procedure(void);
 770  int ufc_dummy_procedure(void) {return 0;}
 771 #endif