nix/libutil/hash.cc

   1 #include "config.h"
   2
   3 #include <iostream>
   4 #include <cstring>
   5
   6 #ifdef HAVE_OPENSSL
   7 #include <openssl/md5.h>
   8 #include <openssl/sha.h>
   9 #else
  10 extern "C" {
  11 #include "md5.h"
  12 #include "sha1.h"
  13 #include "sha256.h"
  14 }
  15 #endif
  16
  17 #include "hash.hh"
  18 #include "archive.hh"
  19 #include "util.hh"
  20
  21 #include <sys/types.h>
  22 #include <sys/stat.h>
  23 #include <fcntl.h>
  24
  25
  26 namespace nix {
  27
  28
  29 Hash::Hash()
  30 {
  31     type = htUnknown;
  32     hashSize = 0;
  33     memset(hash, 0, maxHashSize);
  34 }
  35
  36
  37 Hash::Hash(HashType type)
  38 {
  39     this->type = type;
  40     if (type == htMD5) hashSize = md5HashSize;
  41     else if (type == htSHA1) hashSize = sha1HashSize;
  42     else if (type == htSHA256) hashSize = sha256HashSize;
  43     else throw Error("unknown hash type");
  44     assert(hashSize <= maxHashSize);
  45     memset(hash, 0, maxHashSize);
  46 }
  47
  48
  49 bool Hash::operator == (const Hash & h2) const
  50 {
  51     if (hashSize != h2.hashSize) return false;
  52     for (unsigned int i = 0; i < hashSize; i++)
  53         if (hash[i] != h2.hash[i]) return false;
  54     return true;
  55 }
  56
  57
  58 bool Hash::operator != (const Hash & h2) const
  59 {
  60     return !(*this == h2);
  61 }
  62
  63
  64 bool Hash::operator < (const Hash & h) const
  65 {
  66     for (unsigned int i = 0; i < hashSize; i++) {
  67         if (hash[i] < h.hash[i]) return true;
  68         if (hash[i] > h.hash[i]) return false;
  69     }
  70     return false;
  71 }
  72
  73
  74 const string base16Chars = "0123456789abcdef";
  75
  76
  77 string printHash(const Hash & hash)
  78 {
  79     char buf[hash.hashSize * 2];
  80     for (unsigned int i = 0; i < hash.hashSize; i++) {
  81         buf[i * 2] = base16Chars[hash.hash[i] >> 4];
  82         buf[i * 2 + 1] = base16Chars[hash.hash[i] & 0x0f];
  83     }
  84     return string(buf, hash.hashSize * 2);
  85 }
  86
  87
  88 Hash parseHash(HashType ht, const string & s)
  89 {
  90     Hash hash(ht);
  91     if (s.length() != hash.hashSize * 2)
  92         throw Error(format("invalid hash `%1%'") % s);
  93     for (unsigned int i = 0; i < hash.hashSize; i++) {
  94         string s2(s, i * 2, 2);
  95         if (!isxdigit(s2[0]) || !isxdigit(s2[1]))
  96             throw Error(format("invalid hash `%1%'") % s);
  97         std::istringstream str(s2);
  98         int n;
  99         str >> std::hex >> n;
 100         hash.hash[i] = n;
 101     }
 102     return hash;
 103 }
 104
 105
 106 static unsigned char divMod(unsigned char * bytes, unsigned char y)
 107 {
 108     unsigned int borrow = 0;
 109
 110     int pos = Hash::maxHashSize - 1;
 111     while (pos >= 0 && !bytes[pos]) --pos;
 112
 113     for ( ; pos >= 0; --pos) {
 114         unsigned int s = bytes[pos] + (borrow << 8);
 115         unsigned int d = s / y;
 116         borrow = s % y;
 117         bytes[pos] = d;
 118     }
 119
 120     return borrow;
 121 }
 122
 123
 124 unsigned int hashLength32(const Hash & hash)
 125 {
 126     return (hash.hashSize * 8 - 1) / 5 + 1;
 127 }
 128
 129
 130 // omitted: E O U T
 131 const string base32Chars = "0123456789abcdfghijklmnpqrsvwxyz";
 132
 133
 134 string printHash32(const Hash & hash)
 135 {
 136     Hash hash2(hash);
 137     unsigned int len = hashLength32(hash);
 138
 139     const char * chars = base32Chars.data();
 140
 141     string s(len, '0');
 142
 143     int pos = len - 1;
 144     while (pos >= 0) {
 145         unsigned char digit = divMod(hash2.hash, 32);
 146         s[pos--] = chars[digit];
 147     }
 148
 149     for (unsigned int i = 0; i < hash2.maxHashSize; ++i)
 150         assert(hash2.hash[i] == 0);
 151
 152     return s;
 153 }
 154
 155
 156 string printHash16or32(const Hash & hash)
 157 {
 158     return hash.type == htMD5 ? printHash(hash) : printHash32(hash);
 159 }
 160
 161
 162 static bool mul(unsigned char * bytes, unsigned char y, int maxSize)
 163 {
 164     unsigned char carry = 0;
 165
 166     for (int pos = 0; pos < maxSize; ++pos) {
 167         unsigned int m = bytes[pos] * y + carry;
 168         bytes[pos] = m & 0xff;
 169         carry = m >> 8;
 170     }
 171
 172     return carry;
 173 }
 174
 175
 176 static bool add(unsigned char * bytes, unsigned char y, int maxSize)
 177 {
 178     unsigned char carry = y;
 179
 180     for (int pos = 0; pos < maxSize; ++pos) {
 181         unsigned int m = bytes[pos] + carry;
 182         bytes[pos] = m & 0xff;
 183         carry = m >> 8;
 184         if (carry == 0) break;
 185     }
 186
 187     return carry;
 188 }
 189
 190
 191 Hash parseHash32(HashType ht, const string & s)
 192 {
 193     Hash hash(ht);
 194
 195     const char * chars = base32Chars.data();
 196
 197     for (unsigned int i = 0; i < s.length(); ++i) {
 198         char c = s[i];
 199         unsigned char digit;
 200         for (digit = 0; digit < base32Chars.size(); ++digit) /* !!! slow */
 201             if (chars[digit] == c) break;
 202         if (digit >= 32)
 203             throw Error(format("invalid base-32 hash `%1%'") % s);
 204         if (mul(hash.hash, 32, hash.hashSize) ||
 205             add(hash.hash, digit, hash.hashSize))
 206             throw Error(format("base-32 hash `%1%' is too large") % s);
 207     }
 208
 209     return hash;
 210 }
 211
 212
 213 Hash parseHash16or32(HashType ht, const string & s)
 214 {
 215     Hash hash(ht);
 216     if (s.size() == hash.hashSize * 2)
 217         /* hexadecimal representation */
 218         hash = parseHash(ht, s);
 219     else if (s.size() == hashLength32(hash))
 220         /* base-32 representation */
 221         hash = parseHash32(ht, s);
 222     else
 223         throw Error(format("hash `%1%' has wrong length for hash type `%2%'")
 224             % s % printHashType(ht));
 225     return hash;
 226 }
 227
 228
 229 bool isHash(const string & s)
 230 {
 231     if (s.length() != 32) return false;
 232     for (int i = 0; i < 32; i++) {
 233         char c = s[i];
 234         if (!((c >= '0' && c <= '9') ||
 235               (c >= 'a' && c <= 'f')))
 236             return false;
 237     }
 238     return true;
 239 }
 240
 241
 242 struct Ctx
 243 {
 244     MD5_CTX md5;
 245     SHA_CTX sha1;
 246     SHA256_CTX sha256;
 247 };
 248
 249
 250 static void start(HashType ht, Ctx & ctx)
 251 {
 252     if (ht == htMD5) MD5_Init(&ctx.md5);
 253     else if (ht == htSHA1) SHA1_Init(&ctx.sha1);
 254     else if (ht == htSHA256) SHA256_Init(&ctx.sha256);
 255 }
 256
 257
 258 static void update(HashType ht, Ctx & ctx,
 259     const unsigned char * bytes, unsigned int len)
 260 {
 261     if (ht == htMD5) MD5_Update(&ctx.md5, bytes, len);
 262     else if (ht == htSHA1) SHA1_Update(&ctx.sha1, bytes, len);
 263     else if (ht == htSHA256) SHA256_Update(&ctx.sha256, bytes, len);
 264 }
 265
 266
 267 static void finish(HashType ht, Ctx & ctx, unsigned char * hash)
 268 {
 269     if (ht == htMD5) MD5_Final(hash, &ctx.md5);
 270     else if (ht == htSHA1) SHA1_Final(hash, &ctx.sha1);
 271     else if (ht == htSHA256) SHA256_Final(hash, &ctx.sha256);
 272 }
 273
 274
 275 Hash hashString(HashType ht, const string & s)
 276 {
 277     Ctx ctx;
 278     Hash hash(ht);
 279     start(ht, ctx);
 280     update(ht, ctx, (const unsigned char *) s.data(), s.length());
 281     finish(ht, ctx, hash.hash);
 282     return hash;
 283 }
 284
 285
 286 Hash hashFile(HashType ht, const Path & path)
 287 {
 288     Ctx ctx;
 289     Hash hash(ht);
 290     start(ht, ctx);
 291
 292     AutoCloseFD fd = open(path.c_str(), O_RDONLY);
 293     if (fd == -1) throw SysError(format("opening file `%1%'") % path);
 294
 295     unsigned char buf[8192];
 296     ssize_t n;
 297     while ((n = read(fd, buf, sizeof(buf)))) {
 298         checkInterrupt();
 299         if (n == -1) throw SysError(format("reading file `%1%'") % path);
 300         update(ht, ctx, buf, n);
 301     }
 302
 303     finish(ht, ctx, hash.hash);
 304     return hash;
 305 }
 306
 307
 308 HashSink::HashSink(HashType ht) : ht(ht)
 309 {
 310     ctx = new Ctx;
 311     bytes = 0;
 312     start(ht, *ctx);
 313 }
 314
 315 HashSink::~HashSink()
 316 {
 317     bufPos = 0;
 318     delete ctx;
 319 }
 320
 321 void HashSink::write(const unsigned char * data, size_t len)
 322 {
 323     bytes += len;
 324     update(ht, *ctx, data, len);
 325 }
 326
 327 HashResult HashSink::finish()
 328 {
 329     flush();
 330     Hash hash(ht);
 331     nix::finish(ht, *ctx, hash.hash);
 332     return HashResult(hash, bytes);
 333 }
 334
 335 HashResult HashSink::currentHash()
 336 {
 337     flush();
 338     Ctx ctx2 = *ctx;
 339     Hash hash(ht);
 340     nix::finish(ht, ctx2, hash.hash);
 341     return HashResult(hash, bytes);
 342 }
 343
 344
 345 HashResult hashPath(
 346     HashType ht, const Path & path, PathFilter & filter)
 347 {
 348     HashSink sink(ht);
 349     dumpPath(path, sink, filter);
 350     return sink.finish();
 351 }
 352
 353
 354 Hash compressHash(const Hash & hash, unsigned int newSize)
 355 {
 356     Hash h;
 357     h.hashSize = newSize;
 358     for (unsigned int i = 0; i < hash.hashSize; ++i)
 359         h.hash[i % newSize] ^= hash.hash[i];
 360     return h;
 361 }
 362
 363
 364 HashType parseHashType(const string & s)
 365 {
 366     if (s == "md5") return htMD5;
 367     else if (s == "sha1") return htSHA1;
 368     else if (s == "sha256") return htSHA256;
 369     else return htUnknown;
 370 }
 371
 372
 373 string printHashType(HashType ht)
 374 {
 375     if (ht == htMD5) return "md5";
 376     else if (ht == htSHA1) return "sha1";
 377     else if (ht == htSHA256) return "sha256";
 378     else throw Error("cannot print unknown hash type");
 379 }
 380
 381
 382 }