AppleCSP/open_ssl/misc/rc4_enc.c

   1 /*
   2  * Copyright (c) 2000-2001 Apple Computer, Inc. All Rights Reserved.
   3  *
   4  * The contents of this file constitute Original Code as defined in and are
   5  * subject to the Apple Public Source License Version 1.2 (the 'License').
   6  * You may not use this file except in compliance with the License. Please obtain
   7  * a copy of the License at http://www.apple.com/publicsource and read it before
   8  * using this file.
   9  *
  10  * This Original Code and all software distributed under the License are
  11  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
  12  * OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, INCLUDING WITHOUT
  13  * LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  14  * PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. Please see the License for the
  15  * specific language governing rights and limitations under the License.
  16  */
  17
  18
  19 /* crypto/rc4/rc4_enc.c */
  20 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  21  * All rights reserved.
  22  *
  23  * This package is an SSL implementation written
  24  * by Eric Young (eay@cryptsoft.com).
  25  * The implementation was written so as to conform with Netscapes SSL.
  26  *
  27  * This library is free for commercial and non-commercial use as long as
  28  * the following conditions are aheared to.  The following conditions
  29  * apply to all code found in this distribution, be it the RC4, RSA,
  30  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
  31  * included with this distribution is covered by the same copyright terms
  32  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
  33  *
  34  * Copyright remains Eric Young's, and as such any Copyright notices in
  35  * the code are not to be removed.
  36  * If this package is used in a product, Eric Young should be given attribution
  37  * as the author of the parts of the library used.
  38  * This can be in the form of a textual message at program startup or
  39  * in documentation (online or textual) provided with the package.
  40  *
  41  * Redistribution and use in source and binary forms, with or without
  42  * modification, are permitted provided that the following conditions
  43  * are met:
  44  * 1. Redistributions of source code must retain the copyright
  45  *    notice, this list of conditions and the following disclaimer.
  46  * 2. Redistributions in binary form must reproduce the above copyright
  47  *    notice, this list of conditions and the following disclaimer in the
  48  *    documentation and/or other materials provided with the distribution.
  49  * 3. All advertising materials mentioning features or use of this software
  50  *    must display the following acknowledgement:
  51  *    "This product includes cryptographic software written by
  52  *     Eric Young (eay@cryptsoft.com)"
  53  *    The word 'cryptographic' can be left out if the rouines from the library
  54  *    being used are not cryptographic related :-).
  55  * 4. If you include any Windows specific code (or a derivative thereof) from
  56  *    the apps directory (application code) you must include an acknowledgement:
  57  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
  58  *
  59  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
  60  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  61  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  62  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  63  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  64  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  65  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  66  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  67  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  68  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  69  * SUCH DAMAGE.
  70  *
  71  * The licence and distribution terms for any publically available version or
  72  * derivative of this code cannot be changed.  i.e. this code cannot simply be
  73  * copied and put under another distribution licence
  74  * [including the GNU Public Licence.]
  75  */
  76
  77 #include <openssl/rc4.h>
  78
  79 /* RC4 as implemented from a posting from
  80  * Newsgroups: sci.crypt
  81  * From: sterndark@netcom.com (David Sterndark)
  82  * Subject: RC4 Algorithm revealed.
  83  * Message-ID: <sternCvKL4B.Hyy@netcom.com>
  84  * Date: Wed, 14 Sep 1994 06:35:31 GMT
  85  */
  86
  87 void RC4(RC4_KEY *key, unsigned long len, const unsigned char *indata,
  88              unsigned char *outdata)
  89         {
  90         register RC4_INT *d;
  91         register RC4_INT x,y,tx,ty;
  92         int i;
  93
  94         x=key->x;
  95         y=key->y;
  96         d=key->data;
  97
  98 #if defined(RC4_CHUNK)
  99         /*
 100          * The original reason for implementing this(*) was the fact that
 101          * pre-21164a Alpha CPUs don't have byte load/store instructions
 102          * and e.g. a byte store has to be done with 64-bit load, shift,
 103          * and, or and finally 64-bit store. Peaking data and operating
 104          * at natural word size made it possible to reduce amount of
 105          * instructions as well as to perform early read-ahead without
 106          * suffering from RAW (read-after-write) hazard. This resulted
 107          * in ~40%(**) performance improvement on 21064 box with gcc.
 108          * But it's not only Alpha users who win here:-) Thanks to the
 109          * early-n-wide read-ahead this implementation also exhibits
 110          * >40% speed-up on SPARC and 20-30% on 64-bit MIPS (depending
 111          * on sizeof(RC4_INT)).
 112          *
 113          * (*)  "this" means code which recognizes the case when input
 114          *      and output pointers appear to be aligned at natural CPU
 115          *      word boundary
 116          * (**) i.e. according to 'apps/openssl speed rc4' benchmark,
 117          *      crypto/rc4/rc4speed.c exhibits almost 70% speed-up...
 118          *
 119          * Cavets.
 120          *
 121          * - RC4_CHUNK="unsigned long long" should be a #1 choice for
 122          *   UltraSPARC. Unfortunately gcc generates very slow code
 123          *   (2.5-3 times slower than one generated by Sun's WorkShop
 124          *   C) and therefore gcc (at least 2.95 and earlier) should
 125          *   always be told that RC4_CHUNK="unsigned long".
 126          *
 127          *                                      <appro@fy.chalmers.se>
 128          */
 129
 130 # define RC4_STEP       ( \
 131                         x=(x+1) &0xff,  \
 132                         tx=d[x],        \
 133                         y=(tx+y)&0xff,  \
 134                         ty=d[y],        \
 135                         d[y]=tx,        \
 136                         d[x]=ty,        \
 137                         (RC4_CHUNK)d[(tx+ty)&0xff]\
 138                         )
 139
 140         if ( ( ((unsigned long)indata  & (sizeof(RC4_CHUNK)-1)) |
 141                ((unsigned long)outdata & (sizeof(RC4_CHUNK)-1)) ) == 0 )
 142                 {
 143                 RC4_CHUNK ichunk,otp;
 144                 const union { long one; char little; } is_endian = {1};
 145
 146                 /*
 147                  * I reckon we can afford to implement both endian
 148                  * cases and to decide which way to take at run-time
 149                  * because the machine code appears to be very compact
 150                  * and redundant 1-2KB is perfectly tolerable (i.e.
 151                  * in case the compiler fails to eliminate it:-). By
 152                  * suggestion from Terrel Larson <terr@terralogic.net>
 153                  * who also stands for the is_endian union:-)
 154                  *
 155                  * Special notes.
 156                  *
 157                  * - is_endian is declared automatic as doing otherwise
 158                  *   (declaring static) prevents gcc from eliminating
 159                  *   the redundant code;
 160                  * - compilers (those I've tried) don't seem to have
 161                  *   problems eliminating either the operators guarded
 162                  *   by "if (sizeof(RC4_CHUNK)==8)" or the condition
 163                  *   expressions themselves so I've got 'em to replace
 164                  *   corresponding #ifdefs from the previous version;
 165                  * - I chose to let the redundant switch cases when
 166                  *   sizeof(RC4_CHUNK)!=8 be (were also #ifdefed
 167                  *   before);
 168                  * - in case you wonder "&(sizeof(RC4_CHUNK)*8-1)" in
 169                  *   [LB]ESHFT guards against "shift is out of range"
 170                  *   warnings when sizeof(RC4_CHUNK)!=8
 171                  *
 172                  *                      <appro@fy.chalmers.se>
 173                  */
 174                 if (!is_endian.little)
 175                         {       /* BIG-ENDIAN CASE */
 176 # define BESHFT(c)      (((sizeof(RC4_CHUNK)-(c)-1)*8)&(sizeof(RC4_CHUNK)*8-1))
 177                         for (;len&-sizeof(RC4_CHUNK);len-=sizeof(RC4_CHUNK))
 178                                 {
 179                                 ichunk  = *(RC4_CHUNK *)indata;
 180                                 otp  = RC4_STEP<<BESHFT(0);
 181                                 otp |= RC4_STEP<<BESHFT(1);
 182                                 otp |= RC4_STEP<<BESHFT(2);
 183                                 otp |= RC4_STEP<<BESHFT(3);
 184                                 if (sizeof(RC4_CHUNK)==8)
 185                                         {
 186                                         otp |= RC4_STEP<<BESHFT(4);
 187                                         otp |= RC4_STEP<<BESHFT(5);
 188                                         otp |= RC4_STEP<<BESHFT(6);
 189                                         otp |= RC4_STEP<<BESHFT(7);
 190                                         }
 191                                 *(RC4_CHUNK *)outdata = otp^ichunk;
 192                                 indata  += sizeof(RC4_CHUNK);
 193                                 outdata += sizeof(RC4_CHUNK);
 194                                 }
 195                         if (len)
 196                                 {
 197                                 RC4_CHUNK mask=(RC4_CHUNK)-1, ochunk;
 198
 199                                 ichunk = *(RC4_CHUNK *)indata;
 200                                 ochunk = *(RC4_CHUNK *)outdata;
 201                                 otp = 0;
 202                                 i = BESHFT(0);
 203                                 mask <<= (sizeof(RC4_CHUNK)-len)<<3;
 204                                 switch (len&(sizeof(RC4_CHUNK)-1))
 205                                         {
 206                                         case 7: otp  = RC4_STEP<<i, i-=8;
 207                                         case 6: otp |= RC4_STEP<<i, i-=8;
 208                                         case 5: otp |= RC4_STEP<<i, i-=8;
 209                                         case 4: otp |= RC4_STEP<<i, i-=8;
 210                                         case 3: otp |= RC4_STEP<<i, i-=8;
 211                                         case 2: otp |= RC4_STEP<<i, i-=8;
 212                                         case 1: otp |= RC4_STEP<<i, i-=8;
 213                                         case 0: ; /*
 214                                                    * it's never the case,
 215                                                    * but it has to be here
 216                                                    * for ultrix?
 217                                                    */
 218                                         }
 219                                 ochunk &= ~mask;
 220                                 ochunk |= (otp^ichunk) & mask;
 221                                 *(RC4_CHUNK *)outdata = ochunk;
 222                                 }
 223                         key->x=x;
 224                         key->y=y;
 225                         return;
 226                         }       /* big-endian */
 227                 else
 228                         {       /* LITTLE-ENDIAN CASE */
 229 # define LESHFT(c)      (((c)*8)&(sizeof(RC4_CHUNK)*8-1))
 230                         for (;len&-sizeof(RC4_CHUNK);len-=sizeof(RC4_CHUNK))
 231                                 {
 232                                 ichunk  = *(RC4_CHUNK *)indata;
 233                                 otp  = RC4_STEP;
 234                                 otp |= RC4_STEP<<8;
 235                                 otp |= RC4_STEP<<16;
 236                                 otp |= RC4_STEP<<24;
 237                                 if (sizeof(RC4_CHUNK)==8)
 238                                         {
 239                                         otp |= RC4_STEP<<LESHFT(4);
 240                                         otp |= RC4_STEP<<LESHFT(5);
 241                                         otp |= RC4_STEP<<LESHFT(6);
 242                                         otp |= RC4_STEP<<LESHFT(7);
 243                                         }
 244                                 *(RC4_CHUNK *)outdata = otp^ichunk;
 245                                 indata  += sizeof(RC4_CHUNK);
 246                                 outdata += sizeof(RC4_CHUNK);
 247                                 }
 248                         if (len)
 249                                 {
 250                                 RC4_CHUNK mask=(RC4_CHUNK)-1, ochunk;
 251
 252                                 ichunk = *(RC4_CHUNK *)indata;
 253                                 ochunk = *(RC4_CHUNK *)outdata;
 254                                 otp = 0;
 255                                 i   = 0;
 256                                 mask >>= (sizeof(RC4_CHUNK)-len)<<3;
 257                                 switch (len&(sizeof(RC4_CHUNK)-1))
 258                                         {
 259                                         case 7: otp  = RC4_STEP,    i+=8;
 260                                         case 6: otp |= RC4_STEP<<i, i+=8;
 261                                         case 5: otp |= RC4_STEP<<i, i+=8;
 262                                         case 4: otp |= RC4_STEP<<i, i+=8;
 263                                         case 3: otp |= RC4_STEP<<i, i+=8;
 264                                         case 2: otp |= RC4_STEP<<i, i+=8;
 265                                         case 1: otp |= RC4_STEP<<i, i+=8;
 266                                         case 0: ; /*
 267                                                    * it's never the case,
 268                                                    * but it has to be here
 269                                                    * for ultrix?
 270                                                    */
 271                                         }
 272                                 ochunk &= ~mask;
 273                                 ochunk |= (otp^ichunk) & mask;
 274                                 *(RC4_CHUNK *)outdata = ochunk;
 275                                 }
 276                         key->x=x;
 277                         key->y=y;
 278                         return;
 279                         } /* little-endian */
 280                 }
 281 #endif
 282 #define LOOP(in,out) \
 283                 x=((x+1)&0xff); \
 284                 tx=d[x]; \
 285                 y=(tx+y)&0xff; \
 286                 d[x]=ty=d[y]; \
 287                 d[y]=tx; \
 288                 (out) = d[(tx+ty)&0xff]^ (in);
 289
 290 #ifndef RC4_INDEX
 291 #define RC4_LOOP(a,b,i) LOOP(*((a)++),*((b)++))
 292 #else
 293 #define RC4_LOOP(a,b,i) LOOP(a[i],b[i])
 294 #endif
 295
 296         i=(int)(len>>3L);
 297         if (i)
 298                 {
 299                 for (;;)
 300                         {
 301                         RC4_LOOP(indata,outdata,0);
 302                         RC4_LOOP(indata,outdata,1);
 303                         RC4_LOOP(indata,outdata,2);
 304                         RC4_LOOP(indata,outdata,3);
 305                         RC4_LOOP(indata,outdata,4);
 306                         RC4_LOOP(indata,outdata,5);
 307                         RC4_LOOP(indata,outdata,6);
 308                         RC4_LOOP(indata,outdata,7);
 309 #ifdef RC4_INDEX
 310                         indata+=8;
 311                         outdata+=8;
 312 #endif
 313                         if (--i == 0) break;
 314                         }
 315                 }
 316         i=(int)len&0x07;
 317         if (i)
 318                 {
 319                 for (;;)
 320                         {
 321                         RC4_LOOP(indata,outdata,0); if (--i == 0) break;
 322                         RC4_LOOP(indata,outdata,1); if (--i == 0) break;
 323                         RC4_LOOP(indata,outdata,2); if (--i == 0) break;
 324                         RC4_LOOP(indata,outdata,3); if (--i == 0) break;
 325                         RC4_LOOP(indata,outdata,4); if (--i == 0) break;
 326                         RC4_LOOP(indata,outdata,5); if (--i == 0) break;
 327                         RC4_LOOP(indata,outdata,6); if (--i == 0) break;
 328                         }
 329                 }
 330         key->x=x;
 331         key->y=y;
 332         }