llvm/lib/Support/SipHash.cpp

   1 //===--- SipHash.cpp - An ABI-stable string hash --------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file implements an ABI-stable string hash based on SipHash, used to
  10 //  compute ptrauth discriminators.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Support/SipHash.h"
  15 #include "llvm/ADT/ArrayRef.h"
  16 #include "llvm/ADT/StringExtras.h"
  17 #include "llvm/ADT/StringRef.h"
  18 #include "llvm/Support/Compiler.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/Support/Endian.h"
  21 #include <cstdint>
  22
  23 using namespace llvm;
  24 using namespace support;
  25
  26 #define DEBUG_TYPE "llvm-siphash"
  27
  28 // Lightly adapted from the SipHash reference C implementation:
  29 //   https://github.com/veorq/SipHash
  30 // by Jean-Philippe Aumasson and Daniel J. Bernstein
  31
  32 #define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
  33
  34 #define SIPROUND                                                               \
  35   do {                                                                         \
  36     v0 += v1;                                                                  \
  37     v1 = ROTL(v1, 13);                                                         \
  38     v1 ^= v0;                                                                  \
  39     v0 = ROTL(v0, 32);                                                         \
  40     v2 += v3;                                                                  \
  41     v3 = ROTL(v3, 16);                                                         \
  42     v3 ^= v2;                                                                  \
  43     v0 += v3;                                                                  \
  44     v3 = ROTL(v3, 21);                                                         \
  45     v3 ^= v0;                                                                  \
  46     v2 += v1;                                                                  \
  47     v1 = ROTL(v1, 17);                                                         \
  48     v1 ^= v2;                                                                  \
  49     v2 = ROTL(v2, 32);                                                         \
  50   } while (0)
  51
  52 namespace {
  53
  54 /// Computes a SipHash value
  55 ///
  56 /// \param in: pointer to input data (read-only)
  57 /// \param inlen: input data length in bytes (any size_t value)
  58 /// \param k: reference to the key data 16-byte array (read-only)
  59 /// \returns output data, must be 8 or 16 bytes
  60 ///
  61 template <int cROUNDS, int dROUNDS, size_t outlen>
  62 void siphash(const unsigned char *in, uint64_t inlen,
  63              const unsigned char (&k)[16], unsigned char (&out)[outlen]) {
  64
  65   const unsigned char *ni = (const unsigned char *)in;
  66   const unsigned char *kk = (const unsigned char *)k;
  67
  68   static_assert(outlen == 8 || outlen == 16, "result should be 8 or 16 bytes");
  69
  70   uint64_t v0 = UINT64_C(0x736f6d6570736575);
  71   uint64_t v1 = UINT64_C(0x646f72616e646f6d);
  72   uint64_t v2 = UINT64_C(0x6c7967656e657261);
  73   uint64_t v3 = UINT64_C(0x7465646279746573);
  74   uint64_t k0 = endian::read64le(kk);
  75   uint64_t k1 = endian::read64le(kk + 8);
  76   uint64_t m;
  77   int i;
  78   const unsigned char *end = ni + inlen - (inlen % sizeof(uint64_t));
  79   const int left = inlen & 7;
  80   uint64_t b = ((uint64_t)inlen) << 56;
  81   v3 ^= k1;
  82   v2 ^= k0;
  83   v1 ^= k1;
  84   v0 ^= k0;
  85
  86   if (outlen == 16)
  87     v1 ^= 0xee;
  88
  89   for (; ni != end; ni += 8) {
  90     m = endian::read64le(ni);
  91     v3 ^= m;
  92
  93     for (i = 0; i < cROUNDS; ++i)
  94       SIPROUND;
  95
  96     v0 ^= m;
  97   }
  98
  99   switch (left) {
 100   case 7:
 101     b |= ((uint64_t)ni[6]) << 48;
 102     LLVM_FALLTHROUGH;
 103   case 6:
 104     b |= ((uint64_t)ni[5]) << 40;
 105     LLVM_FALLTHROUGH;
 106   case 5:
 107     b |= ((uint64_t)ni[4]) << 32;
 108     LLVM_FALLTHROUGH;
 109   case 4:
 110     b |= ((uint64_t)ni[3]) << 24;
 111     LLVM_FALLTHROUGH;
 112   case 3:
 113     b |= ((uint64_t)ni[2]) << 16;
 114     LLVM_FALLTHROUGH;
 115   case 2:
 116     b |= ((uint64_t)ni[1]) << 8;
 117     LLVM_FALLTHROUGH;
 118   case 1:
 119     b |= ((uint64_t)ni[0]);
 120     break;
 121   case 0:
 122     break;
 123   }
 124
 125   v3 ^= b;
 126
 127   for (i = 0; i < cROUNDS; ++i)
 128     SIPROUND;
 129
 130   v0 ^= b;
 131
 132   if (outlen == 16)
 133     v2 ^= 0xee;
 134   else
 135     v2 ^= 0xff;
 136
 137   for (i = 0; i < dROUNDS; ++i)
 138     SIPROUND;
 139
 140   b = v0 ^ v1 ^ v2 ^ v3;
 141   endian::write64le(out, b);
 142
 143   if (outlen == 8)
 144     return;
 145
 146   v1 ^= 0xdd;
 147
 148   for (i = 0; i < dROUNDS; ++i)
 149     SIPROUND;
 150
 151   b = v0 ^ v1 ^ v2 ^ v3;
 152   endian::write64le(out + 8, b);
 153 }
 154
 155 } // end anonymous namespace
 156
 157 void llvm::getSipHash_2_4_64(ArrayRef<uint8_t> In, const uint8_t (&K)[16],
 158                              uint8_t (&Out)[8]) {
 159   siphash<2, 4>(In.data(), In.size(), K, Out);
 160 }
 161
 162 void llvm::getSipHash_2_4_128(ArrayRef<uint8_t> In, const uint8_t (&K)[16],
 163                               uint8_t (&Out)[16]) {
 164   siphash<2, 4>(In.data(), In.size(), K, Out);
 165 }
 166
 167 /// Compute an ABI-stable 16-bit hash of the given string.
 168 uint16_t llvm::getPointerAuthStableSipHash(StringRef Str) {
 169   static const uint8_t K[16] = {0xb5, 0xd4, 0xc9, 0xeb, 0x79, 0x10, 0x4a, 0x79,
 170                                 0x6f, 0xec, 0x8b, 0x1b, 0x42, 0x87, 0x81, 0xd4};
 171
 172   uint8_t RawHashBytes[8];
 173   getSipHash_2_4_64(arrayRefFromStringRef(Str), K, RawHashBytes);
 174   uint64_t RawHash = endian::read64le(RawHashBytes);
 175
 176   // Produce a non-zero 16-bit discriminator.
 177   uint16_t Discriminator = (RawHash % 0xFFFF) + 1;
 178   LLVM_DEBUG(
 179       dbgs() << "ptrauth stable hash discriminator: " << utostr(Discriminator)
 180              << " (0x"
 181              << utohexstr(Discriminator, /*Lowercase=*/false, /*Width=*/4)
 182              << ")"
 183              << " of: " << Str << "\n");
 184   return Discriminator;
 185 }