git.notmuchmail.org Git - notmuch/blob - lib/libsha1.c

   1 /*
   2  ---------------------------------------------------------------------------
   3  Copyright (c) 2002, Dr Brian Gladman, Worcester, UK.   All rights reserved.
   4
   5  LICENSE TERMS
   6
   7  The free distribution and use of this software in both source and binary
   8  form is allowed (with or without changes) provided that:
   9
  10    1. distributions of this source code include the above copyright
  11       notice, this list of conditions and the following disclaimer;
  12
  13    2. distributions in binary form include the above copyright
  14       notice, this list of conditions and the following disclaimer
  15       in the documentation and/or other associated materials;
  16
  17    3. the copyright holder's name is not used to endorse products
  18       built using this software without specific written permission.
  19
  20  ALTERNATIVELY, provided that this notice is retained in full, this product
  21  may be distributed under the terms of the GNU General Public License (GPL),
  22  in which case the provisions of the GPL apply INSTEAD OF those given above.
  23
  24  DISCLAIMER
  25
  26  This software is provided 'as is' with no explicit or implied warranties
  27  in respect of its properties, including, but not limited to, correctness
  28  and/or fitness for purpose.
  29  ---------------------------------------------------------------------------
  30  Issue Date: 01/08/2005
  31
  32  This is a byte oriented version of SHA1 that operates on arrays of bytes
  33  stored in memory.
  34 */
  35
  36 #include <string.h>     /* for memcpy() etc.        */
  37
  38 #include "libsha1.h"
  39
  40 #if defined(__cplusplus)
  41 extern "C"
  42 {
  43 #endif
  44
  45 #define SHA1_BLOCK_SIZE  64
  46
  47 #define rotl32(x,n)   (((x) << n) | ((x) >> (32 - n)))
  48 #define rotr32(x,n)   (((x) >> n) | ((x) << (32 - n)))
  49
  50 #define bswap_32(x) ((rotr32((x), 24) & 0x00ff00ff) | (rotr32((x), 8) & 0xff00ff00))
  51
  52 /* The macros __BYTE_ORDER__ and __ORDER_*_ENDIAN__ are GNU C
  53  * extensions. They are also supported by clang as of v3.2 */
  54
  55 #ifdef __BYTE_ORDER__
  56 #  if (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
  57 #    define bsw_32(p,n) \
  58        { int _i = (n); while(_i--) ((uint32_t*)p)[_i] = bswap_32(((uint32_t*)p)[_i]); }
  59 #  elif (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
  60 #    define bsw_32(p,n)
  61 #  else
  62 #    error "unknown byte order"
  63 #  endif
  64 #else
  65 #    error "macro __BYTE_ORDER__ is not defined"
  66 #endif
  67
  68 #define SHA1_MASK   (SHA1_BLOCK_SIZE - 1)
  69
  70 #if 0
  71
  72 #define ch(x,y,z)       (((x) & (y)) ^ (~(x) & (z)))
  73 #define parity(x,y,z)   ((x) ^ (y) ^ (z))
  74 #define maj(x,y,z)      (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
  75
  76 #else   /* Discovered by Rich Schroeppel and Colin Plumb   */
  77
  78 #define ch(x,y,z)       ((z) ^ ((x) & ((y) ^ (z))))
  79 #define parity(x,y,z)   ((x) ^ (y) ^ (z))
  80 #define maj(x,y,z)      (((x) & (y)) | ((z) & ((x) ^ (y))))
  81
  82 #endif
  83
  84 /* Compile 64 bytes of hash data into SHA1 context. Note    */
  85 /* that this routine assumes that the byte order in the     */
  86 /* ctx->wbuf[] at this point is in such an order that low   */
  87 /* address bytes in the ORIGINAL byte stream will go in     */
  88 /* this buffer to the high end of 32-bit words on BOTH big  */
  89 /* and little endian systems                                */
  90
  91 #ifdef ARRAY
  92 #define q(v,n)  v[n]
  93 #else
  94 #define q(v,n)  v##n
  95 #endif
  96
  97 #define one_cycle(v,a,b,c,d,e,f,k,h)            \
  98     q(v,e) += rotr32(q(v,a),27) +               \
  99               f(q(v,b),q(v,c),q(v,d)) + k + h;  \
 100     q(v,b)  = rotr32(q(v,b), 2)
 101
 102 #define five_cycle(v,f,k,i)                 \
 103     one_cycle(v, 0,1,2,3,4, f,k,hf(i  ));   \
 104     one_cycle(v, 4,0,1,2,3, f,k,hf(i+1));   \
 105     one_cycle(v, 3,4,0,1,2, f,k,hf(i+2));   \
 106     one_cycle(v, 2,3,4,0,1, f,k,hf(i+3));   \
 107     one_cycle(v, 1,2,3,4,0, f,k,hf(i+4))
 108
 109 static void sha1_compile(sha1_ctx ctx[1])
 110 {   uint32_t    *w = ctx->wbuf;
 111
 112 #ifdef ARRAY
 113     uint32_t    v[5];
 114     memcpy(v, ctx->hash, 5 * sizeof(uint32_t));
 115 #else
 116     uint32_t    v0, v1, v2, v3, v4;
 117     v0 = ctx->hash[0]; v1 = ctx->hash[1];
 118     v2 = ctx->hash[2]; v3 = ctx->hash[3];
 119     v4 = ctx->hash[4];
 120 #endif
 121
 122 #define hf(i)   w[i]
 123
 124     five_cycle(v, ch, 0x5a827999,  0);
 125     five_cycle(v, ch, 0x5a827999,  5);
 126     five_cycle(v, ch, 0x5a827999, 10);
 127     one_cycle(v,0,1,2,3,4, ch, 0x5a827999, hf(15)); \
 128
 129 #undef  hf
 130 #define hf(i) (w[(i) & 15] = rotl32(                    \
 131                  w[((i) + 13) & 15] ^ w[((i) + 8) & 15] \
 132                ^ w[((i) +  2) & 15] ^ w[(i) & 15], 1))
 133
 134     one_cycle(v,4,0,1,2,3, ch, 0x5a827999, hf(16));
 135     one_cycle(v,3,4,0,1,2, ch, 0x5a827999, hf(17));
 136     one_cycle(v,2,3,4,0,1, ch, 0x5a827999, hf(18));
 137     one_cycle(v,1,2,3,4,0, ch, 0x5a827999, hf(19));
 138
 139     five_cycle(v, parity, 0x6ed9eba1,  20);
 140     five_cycle(v, parity, 0x6ed9eba1,  25);
 141     five_cycle(v, parity, 0x6ed9eba1,  30);
 142     five_cycle(v, parity, 0x6ed9eba1,  35);
 143
 144     five_cycle(v, maj, 0x8f1bbcdc,  40);
 145     five_cycle(v, maj, 0x8f1bbcdc,  45);
 146     five_cycle(v, maj, 0x8f1bbcdc,  50);
 147     five_cycle(v, maj, 0x8f1bbcdc,  55);
 148
 149     five_cycle(v, parity, 0xca62c1d6,  60);
 150     five_cycle(v, parity, 0xca62c1d6,  65);
 151     five_cycle(v, parity, 0xca62c1d6,  70);
 152     five_cycle(v, parity, 0xca62c1d6,  75);
 153
 154 #ifdef ARRAY
 155     ctx->hash[0] += v[0]; ctx->hash[1] += v[1];
 156     ctx->hash[2] += v[2]; ctx->hash[3] += v[3];
 157     ctx->hash[4] += v[4];
 158 #else
 159     ctx->hash[0] += v0; ctx->hash[1] += v1;
 160     ctx->hash[2] += v2; ctx->hash[3] += v3;
 161     ctx->hash[4] += v4;
 162 #endif
 163 }
 164
 165 void sha1_begin(sha1_ctx ctx[1])
 166 {
 167     ctx->count[0] = ctx->count[1] = 0;
 168     ctx->hash[0] = 0x67452301;
 169     ctx->hash[1] = 0xefcdab89;
 170     ctx->hash[2] = 0x98badcfe;
 171     ctx->hash[3] = 0x10325476;
 172     ctx->hash[4] = 0xc3d2e1f0;
 173 }
 174
 175 /* SHA1 hash data in an array of bytes into hash buffer and */
 176 /* call the hash_compile function as required.              */
 177
 178 void sha1_hash(const unsigned char data[], unsigned long len, sha1_ctx ctx[1])
 179 {   uint32_t pos = (uint32_t)(ctx->count[0] & SHA1_MASK),
 180             space = SHA1_BLOCK_SIZE - pos;
 181     const unsigned char *sp = data;
 182
 183     if((ctx->count[0] += len) < len)
 184         ++(ctx->count[1]);
 185
 186     while(len >= space)     /* transfer whole blocks if possible  */
 187     {
 188         memcpy(((unsigned char*)ctx->wbuf) + pos, sp, space);
 189         sp += space; len -= space; space = SHA1_BLOCK_SIZE; pos = 0;
 190         bsw_32(ctx->wbuf, SHA1_BLOCK_SIZE >> 2);
 191         sha1_compile(ctx);
 192     }
 193
 194     memcpy(((unsigned char*)ctx->wbuf) + pos, sp, len);
 195 }
 196
 197 /* SHA1 final padding and digest calculation  */
 198
 199 void sha1_end(unsigned char hval[], sha1_ctx ctx[1])
 200 {   uint32_t    i = (uint32_t)(ctx->count[0] & SHA1_MASK);
 201
 202     /* put bytes in the buffer in an order in which references to   */
 203     /* 32-bit words will put bytes with lower addresses into the    */
 204     /* top of 32 bit words on BOTH big and little endian machines   */
 205     bsw_32(ctx->wbuf, (i + 3) >> 2);
 206
 207     /* we now need to mask valid bytes and add the padding which is */
 208     /* a single 1 bit and as many zero bits as necessary. Note that */
 209     /* we can always add the first padding byte here because the    */
 210     /* buffer always has at least one empty slot                    */
 211     ctx->wbuf[i >> 2] &= 0xffffff80 << 8 * (~i & 3);
 212     ctx->wbuf[i >> 2] |= 0x00000080 << 8 * (~i & 3);
 213
 214     /* we need 9 or more empty positions, one for the padding byte  */
 215     /* (above) and eight for the length count. If there is not      */
 216     /* enough space, pad and empty the buffer                       */
 217     if(i > SHA1_BLOCK_SIZE - 9)
 218     {
 219         if(i < 60) ctx->wbuf[15] = 0;
 220         sha1_compile(ctx);
 221         i = 0;
 222     }
 223     else    /* compute a word index for the empty buffer positions  */
 224         i = (i >> 2) + 1;
 225
 226     while(i < 14) /* and zero pad all but last two positions        */
 227         ctx->wbuf[i++] = 0;
 228
 229     /* the following 32-bit length fields are assembled in the      */
 230     /* wrong byte order on little endian machines but this is       */
 231     /* corrected later since they are only ever used as 32-bit      */
 232     /* word values.                                                 */
 233     ctx->wbuf[14] = (ctx->count[1] << 3) | (ctx->count[0] >> 29);
 234     ctx->wbuf[15] = ctx->count[0] << 3;
 235     sha1_compile(ctx);
 236
 237     /* extract the hash value as bytes in case the hash buffer is   */
 238     /* misaligned for 32-bit words                                  */
 239     for(i = 0; i < SHA1_DIGEST_SIZE; ++i)
 240         hval[i] = (unsigned char)(ctx->hash[i >> 2] >> (8 * (~i & 3)));
 241 }
 242
 243 void sha1(unsigned char hval[], const unsigned char data[], unsigned long len)
 244 {   sha1_ctx    cx[1];
 245
 246     sha1_begin(cx); sha1_hash(data, len, cx); sha1_end(hval, cx);
 247 }
 248
 249 #if defined(__cplusplus)
 250 }
 251 #endif