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