crypt/crypt_util.c

   1 /*
   2  * UFC-crypt: ultra fast crypt(3) implementation
   3  *
   4  * Copyright (C) 1991-1993,1996-1998,2000,2010,2011,2012
   5  * Free Software Foundation, Inc.
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; see the file COPYING.LIB.  If not,
  19  * see <http://www.gnu.org/licenses/>.
  20  *
  21  * @(#)crypt_util.c     2.56 12/20/96
  22  *
  23  * Support routines
  24  *
  25  */
  26
  27 #ifdef DEBUG
  28 #include <stdio.h>
  29 #endif
  30 #include <atomic.h>
  31 #include <string.h>
  32
  33 #ifndef STATIC
  34 #define STATIC static
  35 #endif
  36
  37 #ifndef DOS
  38 #include "ufc-crypt.h"
  39 #else
  40 /*
  41  * Thanks to greg%wind@plains.NoDak.edu (Greg W. Wettstein)
  42  * for DOS patches
  43  */
  44 #include "pl.h"
  45 #include "ufc.h"
  46 #endif
  47 #include "crypt.h"
  48 #include "crypt-private.h"
  49
  50 /* Prototypes for local functions.  */
  51 #ifndef __GNU_LIBRARY__
  52 void _ufc_clearmem (char *start, int cnt);
  53 void _ufc_copymem (char *from, char *to, int cnt);
  54 #endif
  55 #ifdef _UFC_32_
  56 STATIC void shuffle_sb (long32 *k, ufc_long saltbits);
  57 #else
  58 STATIC void shuffle_sb (long64 *k, ufc_long saltbits);
  59 #endif
  60
  61
  62 /*
  63  * Permutation done once on the 56 bit
  64  *  key derived from the original 8 byte ASCII key.
  65  */
  66 static const int pc1[56] = {
  67   57, 49, 41, 33, 25, 17,  9,  1, 58, 50, 42, 34, 26, 18,
  68   10,  2, 59, 51, 43, 35, 27, 19, 11,  3, 60, 52, 44, 36,
  69   63, 55, 47, 39, 31, 23, 15,  7, 62, 54, 46, 38, 30, 22,
  70   14,  6, 61, 53, 45, 37, 29, 21, 13,  5, 28, 20, 12,  4
  71 };
  72
  73 /*
  74  * How much to rotate each 28 bit half of the pc1 permutated
  75  *  56 bit key before using pc2 to give the i' key
  76  */
  77 static const int rots[16] = {
  78   1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1
  79 };
  80
  81 /*
  82  * Permutation giving the key
  83  * of the i' DES round
  84  */
  85 static const int pc2[48] = {
  86   14, 17, 11, 24,  1,  5,  3, 28, 15,  6, 21, 10,
  87   23, 19, 12,  4, 26,  8, 16,  7, 27, 20, 13,  2,
  88   41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48,
  89   44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
  90 };
  91
  92 /*
  93  * The E expansion table which selects
  94  * bits from the 32 bit intermediate result.
  95  */
  96 static const int esel[48] = {
  97   32,  1,  2,  3,  4,  5,  4,  5,  6,  7,  8,  9,
  98    8,  9, 10, 11, 12, 13, 12, 13, 14, 15, 16, 17,
  99   16, 17, 18, 19, 20, 21, 20, 21, 22, 23, 24, 25,
 100   24, 25, 26, 27, 28, 29, 28, 29, 30, 31, 32,  1
 101 };
 102
 103 /*
 104  * Permutation done on the
 105  * result of sbox lookups
 106  */
 107 static const int perm32[32] = {
 108   16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
 109   2,   8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
 110 };
 111
 112 /*
 113  * The sboxes
 114  */
 115 static const int sbox[8][4][16]= {
 116         { { 14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7 },
 117           {  0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8 },
 118           {  4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0 },
 119           { 15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13 }
 120         },
 121
 122         { { 15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10 },
 123           {  3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5 },
 124           {  0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15 },
 125           { 13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9 }
 126         },
 127
 128         { { 10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8 },
 129           { 13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1 },
 130           { 13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7 },
 131           {  1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12 }
 132         },
 133
 134         { {  7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15 },
 135           { 13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9 },
 136           { 10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4 },
 137           {  3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14 }
 138         },
 139
 140         { {  2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9 },
 141           { 14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6 },
 142           {  4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14 },
 143           { 11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3 }
 144         },
 145
 146         { { 12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11 },
 147           { 10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8 },
 148           {  9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6 },
 149           {  4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13 }
 150         },
 151
 152         { {  4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1 },
 153           { 13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6 },
 154           {  1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2 },
 155           {  6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12 }
 156         },
 157
 158         { { 13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7 },
 159           {  1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2 },
 160           {  7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8 },
 161           {  2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11 }
 162         }
 163 };
 164
 165 /*
 166  * This is the initial
 167  * permutation matrix
 168  */
 169 static const int initial_perm[64] = {
 170   58, 50, 42, 34, 26, 18, 10,  2, 60, 52, 44, 36, 28, 20, 12, 4,
 171   62, 54, 46, 38, 30, 22, 14,  6, 64, 56, 48, 40, 32, 24, 16, 8,
 172   57, 49, 41, 33, 25, 17,  9,  1, 59, 51, 43, 35, 27, 19, 11, 3,
 173   61, 53, 45, 37, 29, 21, 13,  5, 63, 55, 47, 39, 31, 23, 15, 7
 174 };
 175
 176 /*
 177  * This is the final
 178  * permutation matrix
 179  */
 180 static const int final_perm[64] = {
 181   40,  8, 48, 16, 56, 24, 64, 32, 39,  7, 47, 15, 55, 23, 63, 31,
 182   38,  6, 46, 14, 54, 22, 62, 30, 37,  5, 45, 13, 53, 21, 61, 29,
 183   36,  4, 44, 12, 52, 20, 60, 28, 35,  3, 43, 11, 51, 19, 59, 27,
 184   34,  2, 42, 10, 50, 18, 58, 26, 33,  1, 41,  9, 49, 17, 57, 25
 185 };
 186
 187 #define ascii_to_bin(c) ((c)>='a'?(c-59):(c)>='A'?((c)-53):(c)-'.')
 188 #define bin_to_ascii(c) ((c)>=38?((c)-38+'a'):(c)>=12?((c)-12+'A'):(c)+'.')
 189
 190 static const ufc_long BITMASK[24] = {
 191   0x40000000, 0x20000000, 0x10000000, 0x08000000, 0x04000000, 0x02000000,
 192   0x01000000, 0x00800000, 0x00400000, 0x00200000, 0x00100000, 0x00080000,
 193   0x00004000, 0x00002000, 0x00001000, 0x00000800, 0x00000400, 0x00000200,
 194   0x00000100, 0x00000080, 0x00000040, 0x00000020, 0x00000010, 0x00000008
 195 };
 196
 197 static const unsigned char bytemask[8]  = {
 198   0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
 199 };
 200
 201 static const ufc_long longmask[32] = {
 202   0x80000000, 0x40000000, 0x20000000, 0x10000000,
 203   0x08000000, 0x04000000, 0x02000000, 0x01000000,
 204   0x00800000, 0x00400000, 0x00200000, 0x00100000,
 205   0x00080000, 0x00040000, 0x00020000, 0x00010000,
 206   0x00008000, 0x00004000, 0x00002000, 0x00001000,
 207   0x00000800, 0x00000400, 0x00000200, 0x00000100,
 208   0x00000080, 0x00000040, 0x00000020, 0x00000010,
 209   0x00000008, 0x00000004, 0x00000002, 0x00000001
 210 };
 211
 212 /*
 213  * do_pc1: permform pc1 permutation in the key schedule generation.
 214  *
 215  * The first   index is the byte number in the 8 byte ASCII key
 216  *  -  second    -      -    the two 28 bits halfs of the result
 217  *  -  third     -   selects the 7 bits actually used of each byte
 218  *
 219  * The result is kept with 28 bit per 32 bit with the 4 most significant
 220  * bits zero.
 221  */
 222 static ufc_long do_pc1[8][2][128];
 223
 224 /*
 225  * do_pc2: permform pc2 permutation in the key schedule generation.
 226  *
 227  * The first   index is the septet number in the two 28 bit intermediate values
 228  *  -  second    -    -  -  septet values
 229  *
 230  * Knowledge of the structure of the pc2 permutation is used.
 231  *
 232  * The result is kept with 28 bit per 32 bit with the 4 most significant
 233  * bits zero.
 234  */
 235 static ufc_long do_pc2[8][128];
 236
 237 /*
 238  * eperm32tab: do 32 bit permutation and E selection
 239  *
 240  * The first index is the byte number in the 32 bit value to be permuted
 241  *  -  second  -   is the value of this byte
 242  *  -  third   -   selects the two 32 bit values
 243  *
 244  * The table is used and generated internally in init_des to speed it up
 245  */
 246 static ufc_long eperm32tab[4][256][2];
 247
 248 /*
 249  * efp: undo an extra e selection and do final
 250  *      permutation giving the DES result.
 251  *
 252  *      Invoked 6 bit a time on two 48 bit values
 253  *      giving two 32 bit longs.
 254  */
 255 static ufc_long efp[16][64][2];
 256
 257 /*
 258  * For use by the old, non-reentrant routines
 259  * (crypt/encrypt/setkey)
 260  */
 261 struct crypt_data _ufc_foobar;
 262
 263 #ifdef __GNU_LIBRARY__
 264 #include <bits/libc-lock.h>
 265
 266 __libc_lock_define_initialized (static, _ufc_tables_lock)
 267 #endif
 268
 269 #ifdef DEBUG
 270
 271 void
 272 _ufc_prbits(a, n)
 273      ufc_long *a;
 274      int n;
 275 {
 276   ufc_long i, j, t, tmp;
 277   n /= 8;
 278   for(i = 0; i < n; i++) {
 279     tmp=0;
 280     for(j = 0; j < 8; j++) {
 281       t=8*i+j;
 282       tmp|=(a[t/24] & BITMASK[t % 24])?bytemask[j]:0;
 283     }
 284     (void)printf("%02x ",tmp);
 285   }
 286   printf(" ");
 287 }
 288
 289 static void
 290 _ufc_set_bits(v, b)
 291      ufc_long v;
 292      ufc_long *b;
 293 {
 294   ufc_long i;
 295   *b = 0;
 296   for(i = 0; i < 24; i++) {
 297     if(v & longmask[8 + i])
 298       *b |= BITMASK[i];
 299   }
 300 }
 301
 302 #endif
 303
 304 #ifndef __GNU_LIBRARY__
 305 /*
 306  * Silly rewrites of 'bzero'/'memset'. I do so
 307  * because some machines don't have
 308  * bzero and some don't have memset.
 309  */
 310
 311 void
 312 _ufc_clearmem(start, cnt)
 313      char *start;
 314      int cnt;
 315 {
 316   while(cnt--)
 317     *start++ = '\0';
 318 }
 319
 320 void
 321 _ufc_copymem(from, to, cnt)
 322      char *from, *to;
 323      int cnt;
 324 {
 325   while(cnt--)
 326     *to++ = *from++;
 327 }
 328 #else
 329 #define _ufc_clearmem(start, cnt)   memset(start, 0, cnt)
 330 #define _ufc_copymem(from, to, cnt) memcpy(to, from, cnt)
 331 #endif
 332
 333 /* lookup a 6 bit value in sbox */
 334
 335 #define s_lookup(i,s) sbox[(i)][(((s)>>4) & 0x2)|((s) & 0x1)][((s)>>1) & 0xf];
 336
 337 /*
 338  * Initialize unit - may be invoked directly
 339  * by fcrypt users.
 340  */
 341
 342 void
 343 __init_des_r(__data)
 344      struct crypt_data * __restrict __data;
 345 {
 346   int comes_from_bit;
 347   int bit, sg;
 348   ufc_long j;
 349   ufc_long mask1, mask2;
 350   int e_inverse[64];
 351   static volatile int small_tables_initialized = 0;
 352
 353 #ifdef _UFC_32_
 354   long32 *sb[4];
 355   sb[0] = (long32*)__data->sb0; sb[1] = (long32*)__data->sb1;
 356   sb[2] = (long32*)__data->sb2; sb[3] = (long32*)__data->sb3;
 357 #endif
 358 #ifdef _UFC_64_
 359   long64 *sb[4];
 360   sb[0] = (long64*)__data->sb0; sb[1] = (long64*)__data->sb1;
 361   sb[2] = (long64*)__data->sb2; sb[3] = (long64*)__data->sb3;
 362 #endif
 363
 364   if(small_tables_initialized == 0) {
 365 #ifdef __GNU_LIBRARY__
 366     __libc_lock_lock (_ufc_tables_lock);
 367     if(small_tables_initialized)
 368       goto small_tables_done;
 369 #endif
 370
 371     /*
 372      * Create the do_pc1 table used
 373      * to affect pc1 permutation
 374      * when generating keys
 375      */
 376     _ufc_clearmem((char*)do_pc1, (int)sizeof(do_pc1));
 377     for(bit = 0; bit < 56; bit++) {
 378       comes_from_bit  = pc1[bit] - 1;
 379       mask1 = bytemask[comes_from_bit % 8 + 1];
 380       mask2 = longmask[bit % 28 + 4];
 381       for(j = 0; j < 128; j++) {
 382         if(j & mask1)
 383           do_pc1[comes_from_bit / 8][bit / 28][j] |= mask2;
 384       }
 385     }
 386
 387     /*
 388      * Create the do_pc2 table used
 389      * to affect pc2 permutation when
 390      * generating keys
 391      */
 392     _ufc_clearmem((char*)do_pc2, (int)sizeof(do_pc2));
 393     for(bit = 0; bit < 48; bit++) {
 394       comes_from_bit  = pc2[bit] - 1;
 395       mask1 = bytemask[comes_from_bit % 7 + 1];
 396       mask2 = BITMASK[bit % 24];
 397       for(j = 0; j < 128; j++) {
 398         if(j & mask1)
 399           do_pc2[comes_from_bit / 7][j] |= mask2;
 400       }
 401     }
 402
 403     /*
 404      * Now generate the table used to do combined
 405      * 32 bit permutation and e expansion
 406      *
 407      * We use it because we have to permute 16384 32 bit
 408      * longs into 48 bit in order to initialize sb.
 409      *
 410      * Looping 48 rounds per permutation becomes
 411      * just too slow...
 412      *
 413      */
 414
 415     _ufc_clearmem((char*)eperm32tab, (int)sizeof(eperm32tab));
 416     for(bit = 0; bit < 48; bit++) {
 417       ufc_long mask1,comes_from;
 418       comes_from = perm32[esel[bit]-1]-1;
 419       mask1      = bytemask[comes_from % 8];
 420       for(j = 256; j--;) {
 421         if(j & mask1)
 422           eperm32tab[comes_from / 8][j][bit / 24] |= BITMASK[bit % 24];
 423       }
 424     }
 425
 426     /*
 427      * Create an inverse matrix for esel telling
 428      * where to plug out bits if undoing it
 429      */
 430     for(bit=48; bit--;) {
 431       e_inverse[esel[bit] - 1     ] = bit;
 432       e_inverse[esel[bit] - 1 + 32] = bit + 48;
 433     }
 434
 435     /*
 436      * create efp: the matrix used to
 437      * undo the E expansion and effect final permutation
 438      */
 439     _ufc_clearmem((char*)efp, (int)sizeof efp);
 440     for(bit = 0; bit < 64; bit++) {
 441       int o_bit, o_long;
 442       ufc_long word_value, mask1, mask2;
 443       int comes_from_f_bit, comes_from_e_bit;
 444       int comes_from_word, bit_within_word;
 445
 446       /* See where bit i belongs in the two 32 bit long's */
 447       o_long = bit / 32; /* 0..1  */
 448       o_bit  = bit % 32; /* 0..31 */
 449
 450       /*
 451        * And find a bit in the e permutated value setting this bit.
 452        *
 453        * Note: the e selection may have selected the same bit several
 454        * times. By the initialization of e_inverse, we only look
 455        * for one specific instance.
 456        */
 457       comes_from_f_bit = final_perm[bit] - 1;         /* 0..63 */
 458       comes_from_e_bit = e_inverse[comes_from_f_bit]; /* 0..95 */
 459       comes_from_word  = comes_from_e_bit / 6;        /* 0..15 */
 460       bit_within_word  = comes_from_e_bit % 6;        /* 0..5  */
 461
 462       mask1 = longmask[bit_within_word + 26];
 463       mask2 = longmask[o_bit];
 464
 465       for(word_value = 64; word_value--;) {
 466         if(word_value & mask1)
 467           efp[comes_from_word][word_value][o_long] |= mask2;
 468       }
 469     }
 470     atomic_write_barrier ();
 471     small_tables_initialized = 1;
 472 #ifdef __GNU_LIBRARY__
 473 small_tables_done:
 474     __libc_lock_unlock(_ufc_tables_lock);
 475 #endif
 476   } else
 477     atomic_read_barrier ();
 478
 479   /*
 480    * Create the sb tables:
 481    *
 482    * For each 12 bit segment of an 48 bit intermediate
 483    * result, the sb table precomputes the two 4 bit
 484    * values of the sbox lookups done with the two 6
 485    * bit halves, shifts them to their proper place,
 486    * sends them through perm32 and finally E expands
 487    * them so that they are ready for the next
 488    * DES round.
 489    *
 490    */
 491
 492   if (__data->sb0 + sizeof (__data->sb0) == __data->sb1
 493       && __data->sb1 + sizeof (__data->sb1) == __data->sb2
 494       && __data->sb2 + sizeof (__data->sb2) == __data->sb3)
 495     _ufc_clearmem(__data->sb0,
 496                   (int)sizeof(__data->sb0)
 497                   + (int)sizeof(__data->sb1)
 498                   + (int)sizeof(__data->sb2)
 499                   + (int)sizeof(__data->sb3));
 500   else {
 501     _ufc_clearmem(__data->sb0, (int)sizeof(__data->sb0));
 502     _ufc_clearmem(__data->sb1, (int)sizeof(__data->sb1));
 503     _ufc_clearmem(__data->sb2, (int)sizeof(__data->sb2));
 504     _ufc_clearmem(__data->sb3, (int)sizeof(__data->sb3));
 505   }
 506
 507   for(sg = 0; sg < 4; sg++) {
 508     int j1, j2;
 509     int s1, s2;
 510
 511     for(j1 = 0; j1 < 64; j1++) {
 512       s1 = s_lookup(2 * sg, j1);
 513       for(j2 = 0; j2 < 64; j2++) {
 514         ufc_long to_permute, inx;
 515
 516         s2         = s_lookup(2 * sg + 1, j2);
 517         to_permute = (((ufc_long)s1 << 4)  |
 518                       (ufc_long)s2) << (24 - 8 * (ufc_long)sg);
 519
 520 #ifdef _UFC_32_
 521         inx = ((j1 << 6)  | j2) << 1;
 522         sb[sg][inx  ]  = eperm32tab[0][(to_permute >> 24) & 0xff][0];
 523         sb[sg][inx+1]  = eperm32tab[0][(to_permute >> 24) & 0xff][1];
 524         sb[sg][inx  ] |= eperm32tab[1][(to_permute >> 16) & 0xff][0];
 525         sb[sg][inx+1] |= eperm32tab[1][(to_permute >> 16) & 0xff][1];
 526         sb[sg][inx  ] |= eperm32tab[2][(to_permute >>  8) & 0xff][0];
 527         sb[sg][inx+1] |= eperm32tab[2][(to_permute >>  8) & 0xff][1];
 528         sb[sg][inx  ] |= eperm32tab[3][(to_permute)       & 0xff][0];
 529         sb[sg][inx+1] |= eperm32tab[3][(to_permute)       & 0xff][1];
 530 #endif
 531 #ifdef _UFC_64_
 532         inx = ((j1 << 6)  | j2);
 533         sb[sg][inx]  =
 534           ((long64)eperm32tab[0][(to_permute >> 24) & 0xff][0] << 32) |
 535            (long64)eperm32tab[0][(to_permute >> 24) & 0xff][1];
 536         sb[sg][inx] |=
 537           ((long64)eperm32tab[1][(to_permute >> 16) & 0xff][0] << 32) |
 538            (long64)eperm32tab[1][(to_permute >> 16) & 0xff][1];
 539         sb[sg][inx] |=
 540           ((long64)eperm32tab[2][(to_permute >>  8) & 0xff][0] << 32) |
 541            (long64)eperm32tab[2][(to_permute >>  8) & 0xff][1];
 542         sb[sg][inx] |=
 543           ((long64)eperm32tab[3][(to_permute)       & 0xff][0] << 32) |
 544            (long64)eperm32tab[3][(to_permute)       & 0xff][1];
 545 #endif
 546       }
 547     }
 548   }
 549
 550   __data->current_saltbits = 0;
 551   __data->current_salt[0] = 0;
 552   __data->current_salt[1] = 0;
 553   __data->initialized++;
 554 }
 555
 556 void
 557 __init_des()
 558 {
 559   __init_des_r(&_ufc_foobar);
 560 }
 561
 562 /*
 563  * Process the elements of the sb table permuting the
 564  * bits swapped in the expansion by the current salt.
 565  */
 566
 567 #ifdef _UFC_32_
 568 STATIC void
 569 shuffle_sb(k, saltbits)
 570      long32 *k;
 571      ufc_long saltbits;
 572 {
 573   ufc_long j;
 574   long32 x;
 575   for(j=4096; j--;) {
 576     x = (k[0] ^ k[1]) & (long32)saltbits;
 577     *k++ ^= x;
 578     *k++ ^= x;
 579   }
 580 }
 581 #endif
 582
 583 #ifdef _UFC_64_
 584 STATIC void
 585 shuffle_sb(k, saltbits)
 586      long64 *k;
 587      ufc_long saltbits;
 588 {
 589   ufc_long j;
 590   long64 x;
 591   for(j=4096; j--;) {
 592     x = ((*k >> 32) ^ *k) & (long64)saltbits;
 593     *k++ ^= (x << 32) | x;
 594   }
 595 }
 596 #endif
 597
 598 /*
 599  * Return false iff C is in the specified alphabet for crypt salt.
 600  */
 601
 602 static bool
 603 bad_for_salt (char c)
 604 {
 605   switch (c)
 606     {
 607     case '0' ... '9':
 608     case 'A' ... 'Z':
 609     case 'a' ... 'z':
 610     case '.': case '/':
 611       return false;
 612
 613     default:
 614       return true;
 615     }
 616 }
 617
 618 /*
 619  * Setup the unit for a new salt
 620  * Hopefully we'll not see a new salt in each crypt call.
 621  * Return false if an unexpected character was found in s[0] or s[1].
 622  */
 623
 624 bool
 625 _ufc_setup_salt_r(s, __data)
 626      const char *s;
 627      struct crypt_data * __restrict __data;
 628 {
 629   ufc_long i, j, saltbits;
 630   char s0, s1;
 631
 632   if(__data->initialized == 0)
 633     __init_des_r(__data);
 634
 635   s0 = s[0];
 636   if(bad_for_salt (s0))
 637     return false;
 638
 639   s1 = s[1];
 640   if(bad_for_salt (s1))
 641     return false;
 642
 643   if(s0 == __data->current_salt[0] && s1 == __data->current_salt[1])
 644     return true;
 645
 646   __data->current_salt[0] = s0;
 647   __data->current_salt[1] = s1;
 648
 649   /*
 650    * This is the only crypt change to DES:
 651    * entries are swapped in the expansion table
 652    * according to the bits set in the salt.
 653    */
 654   saltbits = 0;
 655   for(i = 0; i < 2; i++) {
 656     long c=ascii_to_bin(s[i]);
 657     for(j = 0; j < 6; j++) {
 658       if((c >> j) & 0x1)
 659         saltbits |= BITMASK[6 * i + j];
 660     }
 661   }
 662
 663   /*
 664    * Permute the sb table values
 665    * to reflect the changed e
 666    * selection table
 667    */
 668 #ifdef _UFC_32_
 669 #define LONGG long32*
 670 #endif
 671 #ifdef _UFC_64_
 672 #define LONGG long64*
 673 #endif
 674
 675   shuffle_sb((LONGG)__data->sb0, __data->current_saltbits ^ saltbits);
 676   shuffle_sb((LONGG)__data->sb1, __data->current_saltbits ^ saltbits);
 677   shuffle_sb((LONGG)__data->sb2, __data->current_saltbits ^ saltbits);
 678   shuffle_sb((LONGG)__data->sb3, __data->current_saltbits ^ saltbits);
 679
 680   __data->current_saltbits = saltbits;
 681
 682   return true;
 683 }
 684
 685 void
 686 _ufc_mk_keytab_r(key, __data)
 687      const char *key;
 688      struct crypt_data * __restrict __data;
 689 {
 690   ufc_long v1, v2, *k1;
 691   int i;
 692 #ifdef _UFC_32_
 693   long32 v, *k2;
 694   k2 = (long32*)__data->keysched;
 695 #endif
 696 #ifdef _UFC_64_
 697   long64 v, *k2;
 698   k2 = (long64*)__data->keysched;
 699 #endif
 700
 701   v1 = v2 = 0; k1 = &do_pc1[0][0][0];
 702   for(i = 8; i--;) {
 703     v1 |= k1[*key   & 0x7f]; k1 += 128;
 704     v2 |= k1[*key++ & 0x7f]; k1 += 128;
 705   }
 706
 707   for(i = 0; i < 16; i++) {
 708     k1 = &do_pc2[0][0];
 709
 710     v1 = (v1 << rots[i]) | (v1 >> (28 - rots[i]));
 711     v  = k1[(v1 >> 21) & 0x7f]; k1 += 128;
 712     v |= k1[(v1 >> 14) & 0x7f]; k1 += 128;
 713     v |= k1[(v1 >>  7) & 0x7f]; k1 += 128;
 714     v |= k1[(v1      ) & 0x7f]; k1 += 128;
 715
 716 #ifdef _UFC_32_
 717     *k2++ = (v | 0x00008000);
 718     v = 0;
 719 #endif
 720 #ifdef _UFC_64_
 721     v = (v << 32);
 722 #endif
 723
 724     v2 = (v2 << rots[i]) | (v2 >> (28 - rots[i]));
 725     v |= k1[(v2 >> 21) & 0x7f]; k1 += 128;
 726     v |= k1[(v2 >> 14) & 0x7f]; k1 += 128;
 727     v |= k1[(v2 >>  7) & 0x7f]; k1 += 128;
 728     v |= k1[(v2      ) & 0x7f];
 729
 730 #ifdef _UFC_32_
 731     *k2++ = (v | 0x00008000);
 732 #endif
 733 #ifdef _UFC_64_
 734     *k2++ = v | 0x0000800000008000l;
 735 #endif
 736   }
 737
 738   __data->direction = 0;
 739 }
 740
 741 /*
 742  * Undo an extra E selection and do final permutations
 743  */
 744
 745 void
 746 _ufc_dofinalperm_r(res, __data)
 747      ufc_long *res;
 748      struct crypt_data * __restrict __data;
 749 {
 750   ufc_long v1, v2, x;
 751   ufc_long l1,l2,r1,r2;
 752
 753   l1 = res[0]; l2 = res[1];
 754   r1 = res[2]; r2 = res[3];
 755
 756   x = (l1 ^ l2) & __data->current_saltbits; l1 ^= x; l2 ^= x;
 757   x = (r1 ^ r2) & __data->current_saltbits; r1 ^= x; r2 ^= x;
 758
 759   v1=v2=0; l1 >>= 3; l2 >>= 3; r1 >>= 3; r2 >>= 3;
 760
 761   v1 |= efp[15][ r2         & 0x3f][0]; v2 |= efp[15][ r2 & 0x3f][1];
 762   v1 |= efp[14][(r2 >>= 6)  & 0x3f][0]; v2 |= efp[14][ r2 & 0x3f][1];
 763   v1 |= efp[13][(r2 >>= 10) & 0x3f][0]; v2 |= efp[13][ r2 & 0x3f][1];
 764   v1 |= efp[12][(r2 >>= 6)  & 0x3f][0]; v2 |= efp[12][ r2 & 0x3f][1];
 765
 766   v1 |= efp[11][ r1         & 0x3f][0]; v2 |= efp[11][ r1 & 0x3f][1];
 767   v1 |= efp[10][(r1 >>= 6)  & 0x3f][0]; v2 |= efp[10][ r1 & 0x3f][1];
 768   v1 |= efp[ 9][(r1 >>= 10) & 0x3f][0]; v2 |= efp[ 9][ r1 & 0x3f][1];
 769   v1 |= efp[ 8][(r1 >>= 6)  & 0x3f][0]; v2 |= efp[ 8][ r1 & 0x3f][1];
 770
 771   v1 |= efp[ 7][ l2         & 0x3f][0]; v2 |= efp[ 7][ l2 & 0x3f][1];
 772   v1 |= efp[ 6][(l2 >>= 6)  & 0x3f][0]; v2 |= efp[ 6][ l2 & 0x3f][1];
 773   v1 |= efp[ 5][(l2 >>= 10) & 0x3f][0]; v2 |= efp[ 5][ l2 & 0x3f][1];
 774   v1 |= efp[ 4][(l2 >>= 6)  & 0x3f][0]; v2 |= efp[ 4][ l2 & 0x3f][1];
 775
 776   v1 |= efp[ 3][ l1         & 0x3f][0]; v2 |= efp[ 3][ l1 & 0x3f][1];
 777   v1 |= efp[ 2][(l1 >>= 6)  & 0x3f][0]; v2 |= efp[ 2][ l1 & 0x3f][1];
 778   v1 |= efp[ 1][(l1 >>= 10) & 0x3f][0]; v2 |= efp[ 1][ l1 & 0x3f][1];
 779   v1 |= efp[ 0][(l1 >>= 6)  & 0x3f][0]; v2 |= efp[ 0][ l1 & 0x3f][1];
 780
 781   res[0] = v1; res[1] = v2;
 782 }
 783
 784 /*
 785  * crypt only: convert from 64 bit to 11 bit ASCII
 786  * prefixing with the salt
 787  */
 788
 789 void
 790 _ufc_output_conversion_r(v1, v2, salt, __data)
 791      ufc_long v1, v2;
 792      const char *salt;
 793      struct crypt_data * __restrict __data;
 794 {
 795   int i, s, shf;
 796
 797   __data->crypt_3_buf[0] = salt[0];
 798   __data->crypt_3_buf[1] = salt[1] ? salt[1] : salt[0];
 799
 800   for(i = 0; i < 5; i++) {
 801     shf = (26 - 6 * i); /* to cope with MSC compiler bug */
 802     __data->crypt_3_buf[i + 2] = bin_to_ascii((v1 >> shf) & 0x3f);
 803   }
 804
 805   s  = (v2 & 0xf) << 2;
 806   v2 = (v2 >> 2) | ((v1 & 0x3) << 30);
 807
 808   for(i = 5; i < 10; i++) {
 809     shf = (56 - 6 * i);
 810     __data->crypt_3_buf[i + 2] = bin_to_ascii((v2 >> shf) & 0x3f);
 811   }
 812
 813   __data->crypt_3_buf[12] = bin_to_ascii(s);
 814   __data->crypt_3_buf[13] = 0;
 815 }
 816
 817
 818 /*
 819  * UNIX encrypt function. Takes a bitvector
 820  * represented by one byte per bit and
 821  * encrypt/decrypt according to edflag
 822  */
 823
 824 void
 825 __encrypt_r(__block, __edflag, __data)
 826      char *__block;
 827      int __edflag;
 828      struct crypt_data * __restrict __data;
 829 {
 830   ufc_long l1, l2, r1, r2, res[4];
 831   int i;
 832 #ifdef _UFC_32_
 833   long32 *kt;
 834   kt = (long32*)__data->keysched;
 835 #endif
 836 #ifdef _UFC_64_
 837   long64 *kt;
 838   kt = (long64*)__data->keysched;
 839 #endif
 840
 841   /*
 842    * Undo any salt changes to E expansion
 843    */
 844   _ufc_setup_salt_r("..", __data);
 845
 846   /*
 847    * Reverse key table if
 848    * changing operation (encrypt/decrypt)
 849    */
 850   if((__edflag == 0) != (__data->direction == 0)) {
 851     for(i = 0; i < 8; i++) {
 852 #ifdef _UFC_32_
 853       long32 x;
 854       x = kt[2 * (15-i)];
 855       kt[2 * (15-i)] = kt[2 * i];
 856       kt[2 * i] = x;
 857
 858       x = kt[2 * (15-i) + 1];
 859       kt[2 * (15-i) + 1] = kt[2 * i + 1];
 860       kt[2 * i + 1] = x;
 861 #endif
 862 #ifdef _UFC_64_
 863       long64 x;
 864       x = kt[15-i];
 865       kt[15-i] = kt[i];
 866       kt[i] = x;
 867 #endif
 868       }
 869     __data->direction = __edflag;
 870   }
 871
 872   /*
 873    * Do initial permutation + E expansion
 874    */
 875   i = 0;
 876   for(l1 = 0; i < 24; i++) {
 877     if(__block[initial_perm[esel[i]-1]-1])
 878       l1 |= BITMASK[i];
 879   }
 880   for(l2 = 0; i < 48; i++) {
 881     if(__block[initial_perm[esel[i]-1]-1])
 882       l2 |= BITMASK[i-24];
 883   }
 884
 885   i = 0;
 886   for(r1 = 0; i < 24; i++) {
 887     if(__block[initial_perm[esel[i]-1+32]-1])
 888       r1 |= BITMASK[i];
 889   }
 890   for(r2 = 0; i < 48; i++) {
 891     if(__block[initial_perm[esel[i]-1+32]-1])
 892       r2 |= BITMASK[i-24];
 893   }
 894
 895   /*
 896    * Do DES inner loops + final conversion
 897    */
 898   res[0] = l1; res[1] = l2;
 899   res[2] = r1; res[3] = r2;
 900   _ufc_doit_r((ufc_long)1, __data, &res[0]);
 901
 902   /*
 903    * Do final permutations
 904    */
 905   _ufc_dofinalperm_r(res, __data);
 906
 907   /*
 908    * And convert to bit array
 909    */
 910   l1 = res[0]; r1 = res[1];
 911   for(i = 0; i < 32; i++) {
 912     *__block++ = (l1 & longmask[i]) != 0;
 913   }
 914   for(i = 0; i < 32; i++) {
 915     *__block++ = (r1 & longmask[i]) != 0;
 916   }
 917 }
 918 weak_alias (__encrypt_r, encrypt_r)
 919
 920 void
 921 encrypt(__block, __edflag)
 922      char *__block;
 923      int __edflag;
 924 {
 925   __encrypt_r(__block, __edflag, &_ufc_foobar);
 926 }
 927
 928
 929 /*
 930  * UNIX setkey function. Take a 64 bit DES
 931  * key and setup the machinery.
 932  */
 933
 934 void
 935 __setkey_r(__key, __data)
 936      const char *__key;
 937      struct crypt_data * __restrict __data;
 938 {
 939   int i,j;
 940   unsigned char c;
 941   unsigned char ktab[8];
 942
 943   _ufc_setup_salt_r("..", __data); /* be sure we're initialized */
 944
 945   for(i = 0; i < 8; i++) {
 946     for(j = 0, c = 0; j < 8; j++)
 947       c = c << 1 | *__key++;
 948     ktab[i] = c >> 1;
 949   }
 950   _ufc_mk_keytab_r((char *) ktab, __data);
 951 }
 952 weak_alias (__setkey_r, setkey_r)
 953
 954 void
 955 setkey(__key)
 956      const char *__key;
 957 {
 958   __setkey_r(__key, &_ufc_foobar);
 959 }