path: root/third_party/nix/src/libutil/hash.cc

#include "libutil/hash.hh"

#include <cstring>
#include <iostream>

#include <absl/strings/escaping.h>
#include <fcntl.h>
#include <openssl/md5.h>
#include <openssl/sha.h>
#include <sys/stat.h>
#include <sys/types.h>

#include "libutil/archive.hh"
#include "libutil/istringstream_nocopy.hh"
#include "libutil/util.hh"

namespace nix {

void Hash::init() {
  if (type == htMD5) {
    hashSize = md5HashSize;
  } else if (type == htSHA1) {
    hashSize = sha1HashSize;
  } else if (type == htSHA256) {
    hashSize = sha256HashSize;
  } else if (type == htSHA512) {
    hashSize = sha512HashSize;
  } else {
    abort();
  }
  assert(hashSize <= maxHashSize);
  memset(hash, 0, maxHashSize);
}

bool Hash::operator==(const Hash& h2) const {
  if (hashSize != h2.hashSize) {
    return false;
  }
  for (unsigned int i = 0; i < hashSize; i++) {
    if (hash[i] != h2.hash[i]) {
      return false;
    }
  }
  return true;
}

bool Hash::operator!=(const Hash& h2) const { return !(*this == h2); }

bool Hash::operator<(const Hash& h) const {
  if (hashSize < h.hashSize) {
    return true;
  }
  if (hashSize > h.hashSize) {
    return false;
  }
  for (unsigned int i = 0; i < hashSize; i++) {
    if (hash[i] < h.hash[i]) {
      return true;
    }
    if (hash[i] > h.hash[i]) {
      return false;
    }
  }
  return false;
}

const std::string base16Chars = "0123456789abcdef";

static std::string printHash16(const Hash& hash) {
  char buf[hash.hashSize * 2];
  for (unsigned int i = 0; i < hash.hashSize; i++) {
    buf[i * 2] = base16Chars[hash.hash[i] >> 4];
    buf[i * 2 + 1] = base16Chars[hash.hash[i] & 0x0f];
  }
  return std::string(buf, hash.hashSize * 2);
}

// omitted: E O U T
const std::string base32Chars = "0123456789abcdfghijklmnpqrsvwxyz";

constexpr signed char kUnBase32[] = {
    -1, -1, -1, -1, -1, -1, -1, -1, /* unprintables */
    -1, -1, -1, -1, -1, -1, -1, -1, /* unprintables */
    -1, -1, -1, -1, -1, -1, -1, -1, /* unprintables */
    -1, -1, -1, -1, -1, -1, -1, -1, /* unprintables */
    -1, -1, -1, -1, -1, -1, -1, -1, /* SP..' */
    -1, -1, -1, -1, -1, -1, -1, -1, /* (../ */
    0,  1,  2,  3,  4,  5,  6,  7,  /* 0..7 */
    8,  9,  -1, -1, -1, -1, -1, -1, /* 8..? */
    -1, -1, -1, -1, -1, -1, -1, -1, /* @..G */
    -1, -1, -1, -1, -1, -1, -1, -1, /* H..O */
    -1, -1, -1, -1, -1, -1, -1, -1, /* P..W */
    -1, -1, -1, -1, -1, -1, -1, -1, /* X.._ */
    -1, 10, 11, 12, 13, -1, 14, 15, /* `..g */
    16, 17, 18, 19, 20, 21, 22, -1, /* h..o */
    23, 24, 25, 26, -1, -1, 27, 28, /* p..w */
    29, 30, 31, -1, -1, -1, -1, -1, /* x..DEL */

    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /* high */
};

bool Hash::IsValidBase32(absl::string_view s) {
  static_assert(sizeof(kUnBase32) == 256);

  for (char c : s) {
    if (kUnBase32[static_cast<unsigned char>(c)] == -1) {
      return false;
    }
  }
  return true;
}

static std::string printHash32(const Hash& hash) {
  assert(hash.hashSize);
  size_t len = hash.base32Len();
  assert(len);

  std::string s;
  s.reserve(len);

  for (int n = static_cast<int>(len) - 1; n >= 0; n--) {
    unsigned int b = n * 5;
    unsigned int i = b / 8;
    unsigned int j = b % 8;
    unsigned char c =
        (hash.hash[i] >> j) |
        (i >= hash.hashSize - 1 ? 0 : hash.hash[i + 1] << (8 - j));
    s.push_back(base32Chars[c & 0x1f]);
  }

  return s;
}

std::string printHash16or32(const Hash& hash) {
  return hash.to_string(hash.type == htMD5 ? Base16 : Base32, false);
}

std::string Hash::to_string(Base base, bool includeType) const {
  std::string s;
  if (base == SRI || includeType) {
    s += printHashType(type);
    s += base == SRI ? '-' : ':';
  }
  switch (base) {
    case Base16:
      s += printHash16(*this);
      break;
    case Base32:
      s += printHash32(*this);
      break;
    case Base64:
    case SRI:
      std::string b64;
      absl::Base64Escape(
          std::string(reinterpret_cast<const char*>(hash), hashSize), &b64);
      s += b64;
      break;
  }
  return s;
}

Hash::Hash(const std::string& s, HashType type) : type(type) {
  size_t pos = 0;
  bool isSRI = false;

  auto sep = s.find(':');
  if (sep == std::string::npos) {
    sep = s.find('-');
    if (sep != std::string::npos) {
      isSRI = true;
    } else if (type == htUnknown) {
      throw BadHash("hash '%s' does not include a type", s);
    }
  }

  if (sep != std::string::npos) {
    std::string hts = std::string(s, 0, sep);
    this->type = parseHashType(hts);
    if (this->type == htUnknown) {
      throw BadHash("unknown hash type '%s'", hts);
    }
    if (type != htUnknown && type != this->type) {
      throw BadHash("hash '%s' should have type '%s'", s, printHashType(type));
    }
    pos = sep + 1;
  }

  init();

  size_t size = s.size() - pos;

  if (!isSRI && size == base16Len()) {
    auto parseHexDigit = [&](char c) {
      if (c >= '0' && c <= '9') {
        return c - '0';
      }
      if (c >= 'A' && c <= 'F') {
        return c - 'A' + 10;
      }
      if (c >= 'a' && c <= 'f') {
        return c - 'a' + 10;
      }
      throw BadHash("invalid base-16 hash '%s'", s);
    };

    for (unsigned int i = 0; i < hashSize; i++) {
      hash[i] = parseHexDigit(s[pos + i * 2]) << 4 |
                parseHexDigit(s[pos + i * 2 + 1]);
    }
  }

  else if (!isSRI && size == base32Len()) {
    for (unsigned int n = 0; n < size; ++n) {
      char c = s[pos + size - n - 1];
      unsigned char digit = 0;
      for (digit = 0; digit < base32Chars.size(); ++digit) { /* !!! slow */
        if (base32Chars[digit] == c) {
          break;
        }
      }
      if (digit >= 32) {
        throw BadHash("invalid base-32 hash '%s'", s);
      }
      unsigned int b = n * 5;
      unsigned int i = b / 8;
      unsigned int j = b % 8;
      hash[i] |= digit << j;

      if (i < hashSize - 1) {
        hash[i + 1] |= digit >> (8 - j);
      } else {
        if ((digit >> (8 - j)) != 0) {
          throw BadHash("invalid base-32 hash '%s'", s);
        }
      }
    }
  }

  else if (isSRI || size == base64Len()) {
    std::string d;
    if (!absl::Base64Unescape(std::string(s, pos), &d)) {
      // TODO(grfn): replace this with StatusOr
      throw Error("Invalid Base64");
    }
    if (d.size() != hashSize) {
      throw BadHash("invalid %s hash '%s'", isSRI ? "SRI" : "base-64", s);
    }
    assert(hashSize);
    memcpy(hash, d.data(), hashSize);
  }

  else {
    throw BadHash("hash '%s' has wrong length for hash type '%s'", s,
                  printHashType(type));
  }
}

union Ctx {
  MD5_CTX md5;
  SHA_CTX sha1;
  SHA256_CTX sha256;
  SHA512_CTX sha512;
};

static void start(HashType ht, Ctx& ctx) {
  if (ht == htMD5) {
    MD5_Init(&ctx.md5);
  } else if (ht == htSHA1) {
    SHA1_Init(&ctx.sha1);
  } else if (ht == htSHA256) {
    SHA256_Init(&ctx.sha256);
  } else if (ht == htSHA512) {
    SHA512_Init(&ctx.sha512);
  }
}

static void update(HashType ht, Ctx& ctx, const unsigned char* bytes,
                   size_t len) {
  if (ht == htMD5) {
    MD5_Update(&ctx.md5, bytes, len);
  } else if (ht == htSHA1) {
    SHA1_Update(&ctx.sha1, bytes, len);
  } else if (ht == htSHA256) {
    SHA256_Update(&ctx.sha256, bytes, len);
  } else if (ht == htSHA512) {
    SHA512_Update(&ctx.sha512, bytes, len);
  }
}

static void finish(HashType ht, Ctx& ctx, unsigned char* hash) {
  if (ht == htMD5) {
    MD5_Final(hash, &ctx.md5);
  } else if (ht == htSHA1) {
    SHA1_Final(hash, &ctx.sha1);
  } else if (ht == htSHA256) {
    SHA256_Final(hash, &ctx.sha256);
  } else if (ht == htSHA512) {
    SHA512_Final(hash, &ctx.sha512);
  }
}

Hash hashString(HashType ht, const std::string& s) {
  Ctx ctx{};
  Hash hash(ht);
  start(ht, ctx);
  update(ht, ctx, reinterpret_cast<const unsigned char*>(s.data()), s.length());
  finish(ht, ctx, hash.hash);
  return hash;
}

Hash hashFile(HashType ht, const Path& path) {
  Ctx ctx{};
  Hash hash(ht);
  start(ht, ctx);

  AutoCloseFD fd = open(path.c_str(), O_RDONLY | O_CLOEXEC);
  if (!fd) {
    throw SysError(format("opening file '%1%'") % path);
  }

  std::vector<unsigned char> buf(8192);
  ssize_t n = 0;
  while ((n = read(fd.get(), buf.data(), buf.size())) != 0) {
    checkInterrupt();
    if (n == -1) {
      throw SysError(format("reading file '%1%'") % path);
    }
    update(ht, ctx, buf.data(), n);
  }

  finish(ht, ctx, hash.hash);
  return hash;
}

HashSink::HashSink(HashType ht) : ht(ht) {
  ctx = new Ctx;
  bytes = 0;
  start(ht, *ctx);
}

HashSink::~HashSink() {
  bufPos = 0;
  delete ctx;
}

void HashSink::write(const unsigned char* data, size_t len) {
  bytes += len;
  update(ht, *ctx, data, len);
}

HashResult HashSink::finish() {
  flush();
  Hash hash(ht);
  nix::finish(ht, *ctx, hash.hash);
  return HashResult(hash, bytes);
}

HashResult HashSink::currentHash() {
  flush();
  Ctx ctx2 = *ctx;
  Hash hash(ht);
  nix::finish(ht, ctx2, hash.hash);
  return HashResult(hash, bytes);
}

HashResult hashPath(HashType ht, const Path& path, PathFilter& filter) {
  HashSink sink(ht);
  dumpPath(path, sink, filter);
  return sink.finish();
}

Hash compressHash(const Hash& hash, unsigned int newSize) {
  Hash h;
  h.hashSize = newSize;
  for (unsigned int i = 0; i < hash.hashSize; ++i) {
    h.hash[i % newSize] ^= hash.hash[i];
  }
  return h;
}

HashType parseHashType(const std::string& s) {
  if (s == "md5") {
    return htMD5;
  }
  if (s == "sha1") {
    return htSHA1;
  } else if (s == "sha256") {
    return htSHA256;
  } else if (s == "sha512") {
    return htSHA512;
  } else {
    return htUnknown;
  }
}

std::string printHashType(HashType ht) {
  if (ht == htMD5) {
    return "md5";
  }
  if (ht == htSHA1) {
    return "sha1";
  } else if (ht == htSHA256) {
    return "sha256";
  } else if (ht == htSHA512) {
    return "sha512";
  } else {
    abort();
  }
}

}  // namespace nix